[Leetcode] 42. Trapping Rain Water (javascript)

문제

https://leetcode.com/problems/trapping-rain-water/

문제설명

검은 막대가 n개가 주어질 경우 가둘 수 있는 물의 양(파란색)을 구하는 문제이다.

해결방법

https://leetcode.com/problems/container-with-most-water/
11번 문제를 해결한 방법과 비슷한 방법으로 문제를 해결하였다.
왼쪽 끝 막대와 오른쪽 끝에서 이동을 시작하도록 만든 후,
왼쪽 막대의 최대 높이(left_max)와 오른쪽 막대(right_max)의 최대 높이를 0으로 가정하고 왼쪽, 오른쪽의 index가 만나기 전까지 반복문을 실행한다.
가장 왼쪽에 위치한 막대(height[left])와 가장 오른쪽에 위치한 막대(height[right])의 높이를 비교하고
만약 왼쪽 막대가 오른쪽 막대보다 높고,
왼쪽 막대(height[left]) 의 높이가 left_max 보다 작은 경우 left_max의 높이에서 height[left] 만큼 뺀 높이를 물의 양에 더해준다. (높은 경우엔 left_max 를 갱신)
그 후 왼쪽 index를 오른쪽으로 이동시키기 위해 left ++; 을 해준다.
반대로 오른쪽 막대(height[right]) 의 높이가 right_max 보다 작은 경우 right_max의 높이에서 height[right] 만큼 뺀 높이를 물의 양에 더해준다. (높은 경우엔 right_max 를 갱신)
그 후 오른쪽 index를 왼쪽으로 이동시키기 위해 right --; 을 해준다.

코드

var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let answer = 0;
    let left_max = 0;
    let right_max = 0;
    
    while(left < right) {
        if(height[left] < height[right]) {
            if(height[left] >= left_max) {
                left_max = height[left];
            } else {
                answer += left_max - height[left];
            }
            left ++;
        } else {
            if(height[right] >= right_max) {
                right_max = height[right]
            } else {
                answer += right_max - height[right];
            }
            --right;
        }
    }
    return answer;
};