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.

My Solutions:

方法1：维持一个非递增的stack。遍历高度

• 如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意这里不直接把高度压入栈，而是把坐标压入栈，这样方便在后来算水平距离。

• 当遇到比栈顶高度大的高度，说明有可能会有坑存在，可以装雨水。

  • 此时栈里至少有一个高度，如果只有一个的话，那么不能形成坑，直接跳过

  • 如果多余一个的话，把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界。坑的高度是（这二者较小者-减去坑的高度），长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量

Time: O(n); Space: O(n)

public int trapRainWater(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int i = 0, res = 0;
    while (i < heights.length) {
        if (stack.isEmpty() || heights[i] <= heights[stack.peek()]) {
            stack.push(i);
            i++;
        } else {
            int bottom = stack.pop();
            if (stack.isEmpty()) continue;
            // 注意这里left是不pop出来的，因为可以继续形成坑
            int left = stack.peek();
            // System.out.println("poped bottom = " + bottom + "; left = " + left + "; right = " + i);
            int h = Math.min(heights[i], heights[left]) - heights[bottom], w = i - left - 1;
            int water = h * w;
            // System.out.println("water is " + water);
            res += water;
            // 注意这里是不进行i++的，因为还要继续判断当前的位置是不是还能继续形成坑
        }
    }
    return res;
}a

方法2：

对于每一个柱子来说，找到它两边比它高的棍子高度的较小者，就是这个水柱的高度。

public int trap(int[] height) {
    int sum = 0;
    
    //两端不用考虑
    for (int i = 1; i < height.length - 2; i++) {
        int maxLeft = 0;
        //找到左边最高墙,从当前列从右往左遍历
        for (int j = i - 1; j >= 0; j--) {
            if (height[j] > maxLeft) {
                maxLeft = height[j];
            }
        }
        int maxRight = 0;
        //找出右边最高墙，从当前列从左往右遍历
        for (int j = i + 1; j < height.length; j++) {
            if (height[j] > maxRight) {
                maxRight = height[j];
            }
        }
        //比较两端最高墙，找出较矮的墙
        int min = Math.min(maxLeft, maxRight);
        if (min > height[i]) {
            sum += (min - height[i]);
        }
    }
    return sum;
}

Time: O(N^2); Space: O(1)

方法3：记录下第i列左边和右边最高棍子的高度

public int trap(int[] height) {
    int sum = 0;
    int[] maxLeft = new int[height.length], maxRight = new int[height.length];
    
    for (int i = 1; i < height.length-1; i++) {
        maxLeft[i] = Math.max(maxLeft[i-1], height[i-1]);
    }
    for (int i = height.length-2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i+1], height[i+1]);
    }
    
    for (int i = 1; i < height.length - 1; i++) {
        int min = Math.min(maxLeft[i], maxRight[i]);
        if (min > height[i]) {
            sum += (min-height[i]);
        }
    }
    return sum;
}

Time: O(N); Space: O(N)

方法4：双指针解法

在这个解法中，leftMax和rightMax代表的是height[0..left]和height[right..end]的最高柱子高度。

public int trap(int[] heights) {
    int l = 0, r = heights.length - 1, res = 0;
    int leftMax = heights[0], rightMax = heights[ - 1];
    while (l <= r) {
        leftMax = Math.max(leftMax, heights[l]);
        rightMax = Math.max(rightMax, heights[r]);

        if (leftMax <= rightMax) {
            res += leftMax - heights[l];
            l++;
        } else {
            res += rightMax - heights[r];
            r--;
        }
    }
    return res;
}

此时的l_max是left指针左边的最高柱子，但是r_max并不一定是left指针右边最高的柱子。因为我们只在乎min(l_max, r_max)，对于上图的情况，我们已经知道l_max < r_max了，至于这个r_max是不是右边最大的，不重要，重要的是height[i]能够装的水只和l_max有关。

Time: O(n); Space: O(1)