[数据结构与算法]2021-7-24 42. 接雨水（动态规划，双指针）

注：

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

示例 1：

输入：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：
输入：height = [4,2,0,3,2,5]
输出：9

提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

题解：
方法一：动态规划
对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去height[i]。

朴素的做法是对于数组height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组height 的长度为 n，该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 O(n²)。

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。

创建两个长度为 n 的数组leftMax 和 rightMax。对于0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。

显然，leftMax[0]=height[0]，rightMax[n?1]=height[n?1]。两个数组的其余元素的计算如下：
当 1≤i≤n?1 时，leftMax[i]=max(leftMax[i?1],height[i])；
当 0≤i≤n?2 时，rightMax[i]=max(rightMax[i+1],height[i])。

因此可以正向遍历数组height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。

在得到数组leftMax 和rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于min(leftMax[i],rightMax[i])?height[i]。遍历每个下标位置即可得到能接的雨水总量。

复杂度分析
时间复杂度：O(n)，其中 n 是数组height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次，计算能接的雨水总量还需要遍历一次。

空间复杂度：O(n)，其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。

class Solution {
public:
    int trap(vector<int>& height) {
        int size=height.size();
        if(size==0){
            return 0;
        }
        vector<int> maxleft(size);
        vector<int> maxright(size);
        int result=0;
        maxleft[0]=height[0];
        maxright[size-1]=height[size-1];
        for(int i=1;i<size;i++){
            maxleft[i]=max(maxleft[i-1],height[i]);
        }
        for(int i=size-2;i>=0;i--){
            maxright[i]=max(maxright[i+1],height[i]);
        }
        for(int i=0;i<size;i++){
            result+=(min(maxleft[i],maxright[i])-height[i]);
        }
        return result;
    }
};

方法三：双指针
注意到下标 i 处能接的雨水量由 leftMax[i] 和rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。

维护两个指针left 和right，以及两个变量 leftMax 和 rightMax，初始时left=0,right=n?1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。

当两个指针没有相遇时，进行如下操作：

1. 使用 height[left] 和height[right] 的值更新leftMax 和 rightMax 的值；
2. 如果 height[left]<height[right]，则必有 leftMax<rightMax，下标 left处能接的雨水量等于leftMax?height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加1（即向右移动一位）；（证明见下）
3. 如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下标 right处能接的雨水量等于rightMax?height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right减 1（即向左移动一位）。（证明见下）
4. 当两个指针相遇时，即可得到能接的雨水总量。

如何证明若 height[left] < height[right] 必有 leftmax < rightmax？

这里 height[left] < height[right] 中的 height[right] 就是当前的 rightmax，而 height[left] < height[right]（rightmax）意味着还没找到大于 rightmax 的 leftmax，所以 leftmax < rightmax。
因此，左指针右移的终止条件是找到比 rightmax 大的 leftmax，也就是说一旦左指针终止左移，此时的height[left] 一定是 leftmax，且大于 rightmax。同理，右指针左移的终止条件是找到比 leftmax 大的 rightmax，而此时的 height[right] 就是 rightmax。
复杂度分析
时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。

空间复杂度：O(1)。只需要使用常数的额外空间。

class Solution {
public:
    int trap(vector<int>& height) {
        int size=height.size();
        if(size==0){
            return 0;
        }
        int result=0;
        int left=0;
        int right=size-1;
        int maxleft=height[left];
        int maxright=height[right];
        while(left<right){
            maxleft=max(maxleft,height[left]);
            maxright=max(maxright,height[right]);
            if(height[left]<height[right]){
                result=result+maxleft-height[left];
                left++;
            }
            else{
                result=result+maxright-height[right];
                right--;
            }
        }
        return result;
    }
};