[LeetCode] 42. trapping rain water (python, javascript, two pointer)

각 왼쪽, 오른쪽 끝에서 시작한다.

왼쪽의 벽이 더 높으면 오른쪽에서 안쪽으로 이동하고 (더 큰 벽을 찾아서) 

오른쪽 벽이 더 높다면 왼쪽에서 안쪽으로 이동한다. 

 

만약 현재 왼쪽에서 안쪽으로 이동하는데 지금까지 왼쪽에서 만난 벽 중 가장 높은 위치 lh 보다 

작은 곳이라면 물이 고이므로 lh-height[l] 이런 식으로 더해준다.

 

1. python

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        left,right=0,len(height)-1
        l_max,r_max=height[left],height[right]
        
        amount=0
        while left<right:
            l_max,r_max=max(height[left],l_max),max(height[right],r_max)
            if l_max<=r_max:
                amount+=l_max-height[left]
                left+=1
            else:
                amount+=r_max-height[right]
                right-=1
        
        return amount

 

2. javascript

 

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let l=0;
    let r=height.length-1;
    let sum=0;
    let lh=height[l];
    let rh=height[r];
    while(l<r){
        if(lh<=rh){
           
            l+=1; 
            if(height[l]>=lh){
                lh=height[l];
            }else{
                sum+=lh-height[l];
            }
            
        }else{
            r-=1;
            if(height[r]>=rh){
                rh=height[r];
            }else{
                sum+=rh-height[r];
            }
        }
       
    }
    return sum;
};