LeetCode 题解-42. Trapping Rain Water

对Leetcode 42. Trapping Rain Water 题目的求解。

Problem 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. avatar

Example 1#

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

Analysis#

很经典的一道题目，解决这个问题的关键点在于明白怎么样才能在一个格子里面集到最多的水．不妨假设我们想要知道在第i个格子里面最多可以集聚到多少水．那么，我们很容易发现，取决与height[i+1…n]中最大数和height[0…i-1]中最大数的较小的那个．所以，我们只需要知道左边最大和右边最大即可．那么可以有两种方案．

基于动态规划#

首先从左边遍历一次数组，dp[i] = max(dp[j]) where 0<=j<=i; 同样再从右边向左遍历一次，这样，对于我们就知道左边最大和右边最大的高度了．

基于two-pointer.#

设定两个指针，left, right. 初始时分别设为最左和最右．在每一次迭代中，判断height[left] 和height[right]的大小．为什么要选小的呢？因为其实我们要找的是两个最大值中的最小值，要想找到更大的最小值，自然是要舍弃现在的最小值．只有这样才能找到更大的．

Solution 1#

1
public static int trap(int[] height) {
2
    if (height.length == 0) return 0;
3
    int left = 0;
4
    int right = height.length - 1;
5
    int maxLeft = 0;
6
    int maxRight = 0;
7
    int sum = 0;
8
    while (left < right){
9
        if (height[left] < height[right]){
10
            if (height[left] <= maxLeft){
11
                sum += maxLeft - height[left];
12
            }
13
            else {
14
                maxLeft = height[left];
15
            }
16
            left ++;
17
        }
18
        else {
19
            if (height[right] <= maxRight){
20
                sum += maxRight - height[right];
21
            }
22
            else {
23
                maxRight = height[right];
24
            }
25
            right --;
26
        }
27
    }
28
    return sum;
29
}

Solution 2#

1
public static int trap(int[] height) {
2
    int dp[] = new int [height.length];
3
    int sum = 0;
4
    int max = 0;
5
    for (int i = 0; i < height.length; ++i){
6
        if (max < height[i]) max = height[i];
7
        dp[i] = max;
8
    }
9
    max = 0;
10
    for (int i = height.length-1; i >= 0; --i){
11
        if (max < height[i]) max = height[i];
12
        sum += Math.min(max, dp[i]) - height[i];
13
    }
14
    return sum;
15
}

Solution 3#

1
public static int trap(int [] height){
2
        //using stack
3
        if (height.length == 0) return 0;
4
        Stack<Integer> s = new Stack<Integer>();
5
        int sum = 0;
6
        for (int i = 0; i < height.length; ){
7
            if (s.isEmpty()) s.push(i++);
8
            else if (height[s.peek()] >= height[i]) s.push(i++);
9
            else {
10
                int top = s.pop();
11
                if (!s.isEmpty()){
12
                    sum += (Math.min(height[s.peek()], height[i]) - height[top]) * (i - s.peek() - 1);
13
                }
14
                else continue;
15
            }
16
        }
17
        return sum;
18
    }