[LeetCode] 42. Trapping Rain Water

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:

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 * 104
0 <= height[i] <= 105

接雨水。

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

思路一 - 双指针

首先是双指针解法（two pointer）。思路是对于任意位置 i，在 i 位置上的积水，是由其左右两边较矮的 bar（可以想象为挡板）的高度和 i 位置的高度的差值决定的。即 volume[i] = [Math.min(left[i], right[i]) - A[i]] * 1。这里的 1 是宽度。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int res = 0;
        int leftMax = 0;
        int rightMax = 0;
        while (left < right) {
            // 意味着右边一定有一个挡板 height[right] 可以使当前位置存得住水
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                res += leftMax - height[left];
                left++;
            }
            // 左边一定有一个挡板 height[left] 可以使当前位置存得住水
            else {
                rightMax = Math.max(rightMax, height[right]);
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let res = 0;
    let leftMax = 0;
    let rightMax = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            res += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            res += rightMax - height[right];
            right--;
        }
    }
    return res;
};

思路二 - 单调栈

再来是单调栈的解法。单调栈的思想可以参见84题。动图可以参考这个帖子。这道题为什么可以用单调栈做是因为如果我们能在某个位置上存水（假设 i 好了），那么在 i 左边的挡板必然是要比 i 高的（左边能挡住），当在 i 的右边突然有一个挡板高度比 i 要高的时候，i 的右边也能被挡住了，所以我们就可以结算在 i 位置到底能存多少水了。

对于本题来说，我们寻求的是一个单调递减栈。栈内存的是数组的下标。当遇到一个元素比栈顶元素大的时候，就开始往外 pop 元素。这样被 pop 的坐标对应的水量其实是最低点，左挡板是最低点左边的一个 index，右挡板是当前这个比栈顶元素大的高度。其他计算水量的步骤跟双指针没有区别。

复杂度

时间O(n^2)
空间O(n)

代码

Java实现

class Solution {
    public int trap(int[] height) {
        // corner case
        if (height == null || height.length == 0) {
            return 0;
        }

        // normal case
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int index = stack.pop();
                // 如果栈顶元素一直相等，那么全都pop出去，只留第一个
                while (!stack.isEmpty() && height[stack.peek()] == height[index]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    int start = stack.peek();
                    res += (Math.min(height[start], height[i]) - height[index]) * (i - start - 1);
                }
            }
            stack.add(i);
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    // corner case
    if (height === null || height.length === 0) {
        return 0;
    }

    // normal case
    let stack = [];
    let res = 0;
    for (let i = 0; i < height.length; i++) {
        while (stack.length && height[stack[stack.length - 1]] < height[i]) {
            let index = stack.pop();
            while (
                stack.length &&
                height[stack[stack.length - 1]] == height[index]
            ) {
                stack.pop();
            }
            if (stack.length) {
                let start = stack[stack.length - 1];
                res +=
                    (Math.min(height[start], height[i]) - height[index]) *
                    (i - start - 1);
            }
        }
        stack.push(i);
    }
    return res;
};