GuilinDev

Lc0042

05 August 2008

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 is able to trap after raining.


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

题意和分析

跟84 - Largest Rectangle in Histogram类似，收集雨水，可以用DP或者stack来做。

1) 暴力解法，按照题意，直接计算每个柱子头顶上的雨水量，加起来返回。具体做法：对于数组中的每个元素的顶上，找出下雨后水能达到的最高位置 = 该元素左右两边最大高度的较小值减去当前高度的值。

2) 在暴力方法中，仅仅为了找到最大值每次都要向左和向右扫描一次，所以可以在暴力法的基础上，先存上每个元素的左右最大值，然后左右两个最大值之中，取较小值（不溢出）进行计算，这就是DP的办法。

时间和空间复杂度均为O(n)。

3) 可以不用像方法2的DP 那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到 result。

时间和空间复杂度均为O(n)。

4) 和方法 2的DP 相比，我们不从左和从右分开计算，我们想办法一次完成遍历。 从动态编程方法的示意图中我们注意到，只要 right_max[i] > left_max[i] （元素 0 到元素 6），积水高度将由 left_max 决定，类似地 left_max[i] > right_max[i]（元素 8 到元素 11）。 所以可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。 我们必须在遍历时维护left_max和right_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。

时间复杂度：O(n)。单次遍历的时间O(n)。 空间复杂度：O(1) 的额外空间。left, right, left_max 和 right_max 只需要常数的空间。

代码

  1. DP方法一，维护一个一位dp数组，遍历两遍数组，第一遍遍历dp[i]中存入i位置左边的最大值；然后第二遍遍历，找到dp[i]右边的最大值；然后两个最大值取较小值，跟当前值A[i]比较，如果大于A[i]，将差值存入结果。
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

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int leftHigh = 0;
        int rightHigh = 0;
        
        // 在位置i时找到左右两端的最高柱子，计算当前i位置头顶的最大出水量
        int[] dp = new int[len]; 
        
        int result = 0;
        
        // 第一次遍历将i位置左边的最高柱子，缓存在dp[]中
        for (int i = 0; i < len; i++) {
            dp[i] = leftHigh;
            leftHigh = Math.max(leftHigh, height[i]);
        }
        
        // 第二次遍历计算右边的最高柱子
        // 同时计算左右最高柱子的较矮者，与当前柱子比较一起，得到当前i头上的水
        for (int i = len - 1; i >= 0; i--) {
            dp[i] = Math.min(dp[i], rightHigh); // 现在dp[i]缓存的是当前i位置，与右边比较，取较小值，水才不会溢出
            rightHigh = Math.max(rightHigh, height[i]); // 计算i位置目前为止右边的最高柱子
            int topWater = dp[i] - height[i]; //当前柱子头顶上的水
            if (topWater > 0) {
                result += topWater;
            }
        }
        return result;
    }
}

DP方法二，上面的方法很好理解，但是是两次遍历，可以优化，可以用两个指针left和right分别指向给定数组的首尾，然后两头往中间扫描，在当前两个指针已经扫描过的范围内，先比较两头找出较小值，如果较小值是left指向的值，从左往右扫，相反就从右往左扫；在扫描过程中如果遇到的值比当前的较小值小，将差值存入结果，如果遇到的值比较小值大，重新确定窗口范围，直到left和right指针相遇并且重合。

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) {
        int result = 0, left = 0, right = height.length - 1;
        while (left < right) {
            int min = Math.min(height[left], height[right]);
            if (height[left] == min) {
                left++;
                while (left < right && height[left] < min) {
                    result += min - height[left];
                    left++;
                }
            } else {
                right--;
                while (left < right && height[right] < min) {
                    result += min - height[right];
                    right--;
                }
            }
        }
        return result;
    }
}

上面解法可以更简洁

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int trap(int[] height) {
        int result = 0, left = 0, right = height.length - 1;
        int level = 0;
        while (left < right) {
            int min = height[(height[left] < height[right]) ? left++ : right--];
            level = Math.max(level, min);
            result += level - min;
        }
        return result;
    }
}
  1. Stack的做法，遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。当遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过，如果多余一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0, n = height.length, result = 0;
        while (i < n) {
            if (stack.isEmpty() || height[i] <= height[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int t = stack.pop();
                if (stack.isEmpty()) {
                    continue;
                }
                result += (Math.min(height[i], height[stack.peek()]) - height[t]) * (i - stack.peek() - 1);
            }
        }
        return result;
    }
}
This site is open source. Improve this page.