LeetCode 42：接雨水与双指针

写在前面：该题转载至leetcode力扣 No.42–接雨水 😃

每根柱子上方的水量，取决于左右最高边界中的较低者。双指针每次只结算已经可以确定水位的一侧。

交互演示

演示的地形限制为 3–16 根柱子、0–8 的整数高度；原题范围见下文。回放为每一步保存了状态快照，额外占用空间，不能把演示器的空间开销等同于后面 C 算法的 O(1)。

题目描述：

No.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
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

默认代码模板：

1
2
3

int trap(int* height, int heightSize) {
    
}

题目解析：

左右相向的双指针可以在线性时间内求解，并且只维护常数个变量。

我们以样例1为例：

下雨前：
想象l，r两个指针从左右两端向中间行进，我们需要维护左右两个指针，左右两个指针所经过的最大高度以及最后的返回值：

1

int l=0,r=heightSize-1,sum=0,lMax=0,rMax=0;

在左右指针相遇的时候就已经遍历了全体数组，而一个指针只有在遇到不比他矮的柱子后，他身后经过的空位才能接到雨水，所以只需要对全体数组进行一次遍历，结合遍历过程中指针每一步行进时的反馈，就可以得出全部的接到雨水数，也就是空缺数。

所以我们用一个在左右指针相遇时停止的while循环进行数组遍历：

1
2
3

while(l<r){

}

在每一次遍历中都更新左右指针所经过的最高柱子的高度：

1
2

lMax = lMax>height[l]?lMax:height[l];
rMax = rMax>height[r]?rMax:height[r];

当 lMax <= rMax 时，右侧已经存在不低于 lMax 的边界，所以左指针所在柱子的水量可以确定为 lMax - height[l]。反之，右指针所在柱子的水量为 rMax - height[r]。结算较低边界的一侧，然后移动对应指针：

1
2
3
4
5
6
7
8

if(lMax>rMax){
            sum+=rMax-height[r];
            r--;
        }
        else{
            sum+=lMax-height[l];
            l++;
        }

效果示意：

这样，每次循环只移动一个指针行进一步，而这个指针定然会在两个指针顺利会师前遍历到符合条件的新柱子，而在路上遇到的所有矮柱子都会为sum的增长做贡献。

复杂度：

使用双指针求解只需要遍历一次，而且只需要维护常数个变量，所以空间复杂度是O(1),时间复杂度是O(n)。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int trap(int* height, int heightSize) {
    int l=0,r=heightSize-1,sum=0,lMax=0,rMax=0;
    while(l<r){
        lMax = lMax>height[l]?lMax:height[l];
        rMax = rMax>height[r]?rMax:height[r];
        if(lMax>rMax){
            sum+=rMax-height[r];
            r--;
        }
        else{
            sum+=lMax-height[l];
            l++;
        }
    }
    return sum;
}