[LeetCode] 42. Trapping Rain Water

https://leetcode.com/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

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

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

 

Example 2:

Input: height =[4,2,0,3,2,5]
Output: 9

 

Constraints:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

 

Code :

var trap = function(height) {
    // 만약 높이가 null이거나 길이가 0이라면 0을 반환합니다.
    if (height === null || height.length === 0) {
        return 0;
    }
    
    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;
    
    // 좌우 포인터를 이용하여 최대 높이를 계산합니다.
    while (left < right) {
        if (height[left] < height[right]) {
            // 왼쪽 높이가 오른쪽 높이보다 작을 경우
            // 왼쪽 높이가 현재까지의 최대 높이보다 크거나 같은 경우 최대 높이를 업데이트합니다.
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                // 그렇지 않은 경우 최대 높이에서 현재 높이를 뺀 값을 결과에 더합니다.
                result += leftMax - height[left];
            }
            left++;
        } else {
            // 오른쪽 높이가 왼쪽 높이보다 작을 경우
            // 오른쪽 높이가 현재까지의 최대 높이보다 크거나 같은 경우 최대 높이를 업데이트합니다.
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                // 그렇지 않은 경우 최대 높이에서 현재 높이를 뺀 값을 결과에 더합니다.
                result += rightMax - height[right];
            }
            right--;
        }
    }
    return result; // 담긴 빗물의 총량을 반환합니다.
};

 

Solutions Code :

var trap = function(height) {
    // 배열의 길이를 변수에 할당합니다.
    let n = height.length;
    // 왼쪽과 오른쪽 인덱스를 초기화하고, 왼쪽과 오른쪽의 최대 높이를 저장하는 변수를 초기화합니다.
    let left = 0, right = n - 1, left_max = 0, right_max = 0, water = 0;
    // 왼쪽 포인터가 오른쪽 포인터를 넘지 않는 동안 반복합니다.
    while (left <= right) {
        // 만약 왼쪽 높이가 오른쪽 높이보다 작거나 같은 경우
        if (height[left] <= height[right]) {
            // 왼쪽 높이가 현재까지의 최대 높이보다 큰 경우 최대 높이를 업데이트합니다.
            if (height[left] > left_max) left_max = height[left];
            else {
                // 그렇지 않은 경우 최대 높이에서 현재 높이를 뺀 값을 결과에 더합니다.
                water += left_max - height[left];
            }
            left++; // 왼쪽 포인터를 증가시킵니다.
        } else {
            // 오른쪽 높이가 왼쪽 높이보다 작은 경우
            // 오른쪽 높이가 현재까지의 최대 높이보다 큰 경우 최대 높이를 업데이트합니다.
            if (height[right] > right_max) right_max = height[right];
            else {
                // 그렇지 않은 경우 최대 높이에서 현재 높이를 뺀 값을 결과에 더합니다.
                water += right_max - height[right];
            }
            right--; // 오른쪽 포인터를 감소시킵니다.
        }
    }
    return water; // 담긴 빗물의 총량을 반환합니다.
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode