Leetcode(42) Trapping Rain Water

发表于 | 更新于 | 分类于

Description

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

img
The above elevation map 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. Thanks Marcos for contributing this image!

Example:

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

解法

遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时我们栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过，如果多余一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量啦。注意，每次碰到比栈顶高的条目，一直做坑的探查，直到碰到比栈顶高的或栈为空再将该条目入栈。每次运算，只计算了比当前条目矮的部分的水，没有计算当前条目高度以上的水。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int trap(int[] height) {
        Stack<Integer> s = new Stack();
        if (height.length <= 2) {
            return 0;
        }
        int result = 0;
        int i = 0;
        while (i < height.length) {
            if (s.empty() || height[i] < height[s.peek()]) {
                s.push(i++);
            } else {
                int con = s.pop();
                if (s.empty()) {
                    continue;
                }
                result += (Math.min(height[i], height[s.peek()]) - height[con]) * (i - s.peek() - 1);
            }
        }
        return result;
    }
}

另一种更加容易想到的解法：

对于每一个位置而言，这个位置的含水量取决于这个位置左右两侧的最大高度的最小值，那么我们先遍历两遍数组，记录每个位置左右两侧的最大高度，然后在遍历一遍数组，根据左右最大高度与自身高度计算该位置的储水量即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        leftMax[0] = height[0];
        for(int i = 1;i<height.length;i++){
            if(leftMax[i-1]<=height[i]){
                leftMax[i] = height[i];
            }
            else{
                leftMax[i] = leftMax[i-1];
            }
        }
        rightMax[height.length - 1] = height[height.length - 1];
        for(int i = height.length - 2;i>=0;i--){
            if(rightMax[i+1]<=height[i]){
                rightMax[i] = height[i];
            }
            else{
                rightMax[i] = rightMax[i+1];
            }
        }
        int res = 0;
        for(int i = 0;i<height.length;i++){
            if(leftMax[i] > height[i] && rightMax[i] > height[i]){
                int minMax = leftMax[i] > rightMax[i] ? rightMax[i] : leftMax[i];
                res += (minMax - height[i]);
            }
        }
        return res;
    }
}