接雨水重要题型

2021-03-23

42. 接雨水

难度困难2179

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

1
2
3

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1 2	输入：height = [4,2,0,3,2,5] 输出：9

提示：

n == height.length
0 <= n <= 3 * 10^4
0 <= height[i] <= 10^5

暴力求解

public int trap(int[] height) {
    int ans = 0;
    int size = height.length;
    for (int i = 1; i < size - 1; i++) {
        int max_left = 0, max_right = 0;
        for (int j = i; j >= 0; j--) { //Search the left part for max bar size
            max_left = Math.max(max_left, height[j]);
        }
        for (int j = i; j < size; j++) { //Search the right part for max bar size
            max_right = Math.max(max_right, height[j]);
        }
        ans += Math.min(max_left, max_right) - height[i];
    }
    return ans;
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划

public int trap(int[] height) {
    if (height == null || height.length == 0)
        return 0;
    int ans = 0;
    int size = height.length;
    int[] left_max = new int[size];
    int[] right_max = new int[size];
    left_max[0] = height[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

单调栈

单调栈的维护是 O(n) 级的时间复杂度，因为所有元素只会进入栈一次，并且出栈后再也不会进栈了。

单调栈的性质：

单调栈里的元素具有单调性;
元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除;
使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。

public int trap(int[] height) {
    int ans = 0, current = 0;
    Deque<Integer> stack = new LinkedList<Integer>();

    while (current < height.length) {
        while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
            // 当前最低的区域
            int top = stack.pop();
            if (stack.isEmpty())
                break;
            // 最低的前面的一个区域
            int distance = current - stack.peek() - 1;
            // 当前的是最低的后面的一个,stack.peek()是最低的前面的一个
            int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
            ans += distance * bounded_height;
        }
        stack.push(current++);
    }
    return ans;
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

双指针

双指针法真的妙，那么如何理解双指针法呢？听我来给你捋一捋。（捋的过程和原解中的C++在细节方面的处理是有出入的）

我们先明确几个变量的意思：

left_max：左边的最大值，它是从左往右遍历找到的
right_max：右边的最大值，它是从右往左遍历找到的
left：从左往右处理的当前下标
right：从右往左处理的当前下标

定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。

定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）

定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

                                   right_max
 left_max                             __
   __                                |  |
  |  |__   __??????????????????????  |  |
__|     |__|                       __|  |__
        left                      right

对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

上述内容引用自：
Lucien的评论

只要左边目前的最大值小于右边目前的最大值，那么当前位置盛水的能力就由左边的最大值决定，直接处理左边的部分，否则目前盛水的最大值由右边决定，需要从右边开始处理。

如果右边目前的最大值小于左边目前的最大值，那么当前位置盛水的能力就由右边的最大值决定，直接处理右边的部分，否则目前盛水的最大值由左边决定，需要从左边开始处理。

class Solution {
    public int trap(int[] height) {

        int n=height.length;
        int l=0,r=n-1;
        int leftMax=0,rightMax=0;

        int ans=0;
        while(l<=r){
            
            if(leftMax<rightMax){
                ans += Math.max(leftMax-height[l],0);
                leftMax = Math.max(height[l],leftMax);   
                l++;
            }else{
                ans += Math.max(rightMax-height[r],0);
                rightMax = Math.max(height[r],rightMax);   
                r--;
            }
        }
        return ans;
    }
}

class Solution {
    public int trap(int[] height) {

        int n=height.length;
        int l=0,r=n-1;
        int leftMax=0,rightMax=0;

        int ans=0;
        while(l<r){
            if(height[l]<height[r]){
                if(height[l]<leftMax){
                    ans += (leftMax-height[l]);
                }else{
                    leftMax = height[l];   
                }
                l++;
            }else{
                if(height[r]<rightMax){
                    ans += (rightMax-height[r]);
                }else{
                    rightMax = height[r];
                }
                r--;
            }
        }
        return ans;
    }
}