Leetcode42. 接雨水

题目描述

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

示例 1：

img

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 * 104
  • 0 <= height[i] <= 105

解题思路

我们可以一列一列地观察规律，发现每一列能够承接的雨水为**这一列左边的最大值和右边的最大值的最小值减去当前列的高度得到的值。**如何求解每一列能都承接的雨水，我们可以有不同的解法。

方法一：动态规划法

这里的动态规划的思想主要体现在求解每一列左侧和右侧的最大值上。

我们用一个leftMaxleftMax数组来保存到第ii列为止它左侧的最大值，那么它的状态转移方程就为：

leftMax[i]=max(leftMax[i−1],height[i])1≤i≤n−1leftMax[i]=max(leftMax[i−1],height[i]) \qquad 1 \leq i \leq n-1

我们用一个rightMaxrightMax数组来保存到第ii列为止它右侧的最大值，那么它的状态转移方程就为：

rightMax[i]=max(rightMax[i+1],height[i])0≤i≤n−2rightMax[i]=max(rightMax[i+1],height[i]) \qquad 0 \leq i \leq n-2

然后就可以根据每一列的leftMaxleftMax和rightMaxrightMax来求得这一列能够承接的雨水，然后遍历每一列，将其加起来就可以得到答案。

方法二：双指针法

方法一的时间复杂度已经为O(n)\mathcal{O}(n)，但是空间复杂度也为O(n)\mathcal{O}(n)，我们可以想办法优化一下空间复杂度。

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

维护两个指针 leftleft 和 rightright，以及两个变量 leftMaxleftMax 和 rightMaxrightMax，初始时 left=0\textit{left}=0,right=n−1\textit{right}=n-1,leftMax=0\textit{leftMax}=0,rightMax=0\textit{rightMax}=0。指针 left\textit{left} 只会向右移动，指针 rightright 只会向左移动，在移动指针的过程中维护两个变量 leftMaxleftMax 和 rightMaxrightMax 的值。

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

  • 使用 height[left]height[left] 和 height[right]height[right] 的值更新 leftMaxleftMax 和 rightMaxrightMax 的值；

  • 如果 height[left]<height[right]height[left]<height[right]，则必有leftMax<rightMaxleftMax<rightMax，下标 $left $处能接的雨水量等于 leftMax−height[left]leftMax−height[left]，将下标 $left $处能接的雨水量加到能接的雨水总量，然后将 $left $加 1（即向右移动一位）；

  • 如果 height[left]≥height[right]height[left] \geq height[right]，则必有 leftMax≥rightMaxleftMax \geq rightMax，下标 $right $处能接的雨水量等于 rightMax−height[right]rightMax−height[right]，将下标 $right $处能接的雨水量加到能接的雨水总量，然后将 $right $减 1（即向左移动一位）。

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

上面操作中理解的难点就是标黑的两句话，有必要再详细解释一下。leftMaxleftMax可以求得下标 $left $列的左侧最大值， rightMaxrightMax 可以求得下标 $right $列的右侧最大值，但是在两个指针没有相遇的时候，下标 $left $列到下标 $right $列之间的列的左右两侧最大值的信息是不完整的，这也就是双指针算法理解的难点。

为了理解这个算法的正确性，我们从双指针法的指针更新条件入手。leftleft指针向右滑动的条件是height[left]<height[right]height[left]<height[right]，此时 leftMaxleftMax就是下标 $left 列的左侧最大值，而且由指针滑动的条件可以得出列的左侧最大值，而且由指针滑动的条件可以得出leftMax < height[right]$。假设下标 $left 列的右侧最大值为列的右侧最大值为assumeMax，那么，那么assumeMax \geq rightMax，而，而rightMax \geq height[right]，所以综合可得，所以综合可得leftMax \leq assumeMax$。因而，下标 $left $处能接的雨水量等于 leftMax−height[left]leftMax−height[left]。

同理，可以推出如果 height[left]≥height[right]height[left] \geq height[right]，则必有 leftMax≥rightMaxleftMax \geq rightMax，下标 $right $处能接的雨水量等于 rightMax−height[right]rightMax−height[right]。

方法二的空间复杂度就优化到了O(1)\mathcal{O}(1)。

根据以上两种算法思想，我们可以写出示例代码。

示例代码

方法一：动态规划法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int trap(vector<int>&height)
{
    if(height.empty()) return 0;

    vector<int>leftMax(height.size(),0);
    leftMax[0]=height[0];
    for(int i=1;i<height.size();++i)
    {
        leftMax[i]=max(leftMax[i-1],height[i]);
    }

    vector<int>rightMax(height.size(),0);
    rightMax[height.size()-1]=height[height.size()-1];
    for(int i=height.size()-2;i>=0;--i)
    {
        rightMax[i]=max(rightMax[i+1],height[i]);
    }

    int res=0;
    for(int i=0;i<height.size();++i)
    {
        int curMin=min(leftMax[i],rightMax[i]);
        if(curMin>height[i]) res+=curMin-height[i];
    }

    return res;
}

方法二：双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int trap(vector<int>&height)
{
    int ans=0;
    int left=0,right=height.size()-1;
    int leftMax=0,rightMax=0;
    while(left<right)
    {
        leftMax=max(leftMax,height[left]);
        rightMax=max(rightMax,height[right]);
        if(height[left]<height[right])
        {
            ans+=leftMax-height[left];
            ++left;
        }
        else{
            ans+=rightMax-height[right];
            --right;
        }
    }
    return ans;
}