42. Trapping Rain Water

[Tcdian]

42. Trapping Rain Water

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

Example

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

[Tcdian]

Solution ( Two Pointers )

• JavaScript Solution

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let result = 0;
    let left = 0;
    let right = height.length - 1;
    let leftMaxHeight = 0;
    let rightMaxHeight = 0;

    while (left < right) {
        const leftHeight = height[left];
        const rightHeight = height[right];
        if (leftHeight < rightHeight) {
            if (leftHeight < leftMaxHeight) {
                result += leftMaxHeight - leftHeight;
            } else {
                leftMaxHeight = leftHeight;
            }
            left++;
        } else {
            if (rightHeight < rightMaxHeight) {
                result += rightMaxHeight - rightHeight;
            } else {
                rightMaxHeight = rightHeight;
            }
            right--;
        }
    }
    
    return result;
};