leetcode解题: Trapping Rain Water (42)

发表于 | 分类于

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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

alt text
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!

解法1: 两遍扫描 O(N) Time O(N) Space

这题和Product of Array except itself有点类似。对于每一个bar，顶端是否能储水取决于左面和右面是否有比它高的bar，假设有而且较低的bar的高度是h，那么对于现在这个bar能储水的量就是h-height。
由此我们可以得出一个思路：对于每一个bar，计算出左边和右边的最高的bar。
在计算右面的bar的时候，我们不必要维护一个新的数组，而是用一个变量就可以了。
Java

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
36
37
public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        // write your code here
        
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int n = heights.length;
        
        if (n < 3) {
            return 0;
        }
        
        
        int[] leftHeight = new int[heights.length];
        
        for (int i =1; i < n; i++) {
            leftHeight[i] = Math.max(leftHeight[i - 1], heights[i - 1]);
        }
        
        int rightHeight = 0;
        
        int sum = 0;
        for (int i = n - 2; i >= 0; i--) {
            rightHeight = Math.max(rightHeight, heights[i + 1]);
            sum += Math.max(0, Math.min(leftHeight[i], rightHeight) - heights[i]);
        }
        
        return sum;
        
    }
}

解法2：Stack, O(N) Time O(N) Space

这题也可以用stack来做。但感觉stack比较容易错。
stack的思路是，要存水必须有一个凹槽。那么我们用stack维护一个递减的数列，遇到比现在的top的数更大的时候就知道有水可以存储了。
当前的top即是凹槽的底，弹出top之后如果还不是空，则继续比较top和当前的bar的高度，如果当前bar还高，那么存储的水就是top - bottom 乘上距离。
这里有一个地方容易错就是，如果当前的height不比top高，那么这个时候也要存储结果。
Java

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
public class Solution {
    public int trap(int[] height) {
        
        if (height == null || height.length == 0) {
            return 0;
        }
        
        if (height.length < 3) {
            return 0;
        }
        
        // Stack stores the index of a element in the array
        Stack<Integer> stack = new Stack<Integer>();
        
        stack.push(0);
        
        int res = 0;
        for (int i = 1; i < height.length; ++i) {
            if (height[i] > height[stack.peek()]) {
                int bottom = height[stack.peek()];
                stack.pop();
                while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                    res += (height[stack.peek()] - bottom) * (i - stack.peek() - 1);
                    bottom = height[stack.pop()];
                }
                if (!stack.isEmpty()) {
                    res += (height[i] - bottom) * ( i - stack.peek() - 1);	//这地方容易漏掉
                }
            }
            stack.push(i);
        }
        return res;
    }
}