🚩[NC]128. 接雨水

🚩传送门：牛客题目

题目

给定 个非负整数表示每个宽度为 **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

解题思路：双指针

我们不难发现，当能蓄水的时候，无非下面两种情况。

1. 双指针从左向右检查，遇到 时，将临时统计蓄水量 累加到答案 上
2. 双指针从右向左检查，遇到 时，将临时统计蓄水量 累加到答案 上
3. 左右两轮的检查后的总的答案 就是真正的蓄水量

复杂度分析

时间复杂度： ，双指针总计遍历整个数组 2 次。

空间复杂度： ，只需要额外的常数级别的空间。

我的代码

public class Solution {
    public long maxWater (int[] arr) {
        // right指针在前,left指针在后
        int left=0;
        int right=0;
        long sum=0;
        long res=0;
        //1. 从左向右检查蓄水池
        while(right<arr.length){
            if(arr[left]>arr[right]){
                sum+=arr[left]-arr[right];
            }else{
                res+=sum;
                sum=0;
                left=right;
            }
            right++;
        }
        // left指针在前,right指针在后
        left=arr.length-1;
        right=left;
        sum=0;
        //2. 从右向左检查蓄水池
        while(left>=0){
            if(arr[right]>arr[left]){
                sum+=arr[right]-arr[left];
            }else{
                res+=sum;
                sum=0;
                right=left;
            }
            left--;
        }
        //3. 返回结果
        return res;
    }
}

通过上图我们发现，当第一次从左向右遍历做完，我们第二次的遍历从右向左不需要全部全部遍历完，执行需要遍历到 处 即可。因为答案只有 右半边 的还没有解出来 。
但是，但是，但是，依然可以简化，因为第一次遍历的时候 **left右半边** 也可以省略

解题思路：至尊版双指针

两个指针 和 ，两个变量 和 ，初始时 ,, , 。指针 只会向右移动，指针 只会向左移动，在移动指针的过程中维护两个变量 和 的值。
当两个指针没有相遇时，进行如下操作：

• 使用 和 的值更新 和 的值；
• 如果 ，则必有

  - 下标 ![](https://cdn.nlark.com/yuque/__latex/7a50ac54e7ed05ea29d7c3eb06e4c555.svg#card=math&code=%5Ctext%7Bleft%7D&id=QBLWz) 处能接的雨水量等于 ![](https://cdn.nlark.com/yuque/__latex/ada534f9aa3ba8bef3414bc3ef2cc0ab.svg#card=math&code=%5Ctext%7BleftMax%E2%88%92height%5Bleft%5D%7D&id=a9zY6)
  - 下标 ![](https://cdn.nlark.com/yuque/__latex/7a50ac54e7ed05ea29d7c3eb06e4c555.svg#card=math&code=%5Ctext%7Bleft%7D&id=o65Nk) 处能接的雨水量加到能接的雨水总量![](https://cdn.nlark.com/yuque/__latex/57c8a6755dfc1e5135044553ac679c08.svg#card=math&code=%5Ctext%7Bans%7D&id=BRGgD) ，然后将 ![](https://cdn.nlark.com/yuque/__latex/7a50ac54e7ed05ea29d7c3eb06e4c555.svg#card=math&code=%5Ctext%7Bleft%7D&id=qYcGo) 加 ![](https://cdn.nlark.com/yuque/__latex/53072c2388d69edc65c2377681e4e87c.svg#card=math&code=1&id=ak79N)（即向右移动一位）；

• 如果 ，则必有

  - 下标 ![](https://cdn.nlark.com/yuque/__latex/622a0dc476db8ccfc3b26c8297e8746e.svg#card=math&code=%5Ctext%7Bright%7D&id=gxaoF)处能接的雨水量等于 ![](https://cdn.nlark.com/yuque/__latex/634bf7cbddb6c6780de22c6a1777df64.svg#card=math&code=%5Ctext%7BrightMax%E2%88%92height%5Bright%5D%7D&id=C6zTe) 
  - 下标 ![](https://cdn.nlark.com/yuque/__latex/622a0dc476db8ccfc3b26c8297e8746e.svg#card=math&code=%5Ctext%7Bright%7D&id=lMYPG)处能接的雨水量加到能接的雨水总量 ![](https://cdn.nlark.com/yuque/__latex/b6c262a1ae972f9d5c381d97ef1bf515.svg#card=math&code=ans&id=N6jCD)，然后将 ![](https://cdn.nlark.com/yuque/__latex/622a0dc476db8ccfc3b26c8297e8746e.svg#card=math&code=%5Ctext%7Bright%7D&id=FDqQr)减 ![](https://cdn.nlark.com/yuque/__latex/53072c2388d69edc65c2377681e4e87c.svg#card=math&code=1&id=jwk0L)（即向左移动一位）。

当两个指针相遇时，即可得到能接的雨水总量。

复杂度分析

时间复杂度： ，两个指针的移动总次数不超过 。

空间复杂度： ，只需要额外的常数级别的空间。

我的代码

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}