接雨水

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

解法一（动态规划 + 双指针）：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int>suf(n + 1);
        suf[n] = INT_MIN;
        for (int i = n - 1; i >= 0; i--)
        {
            if (height[i] >= suf[i + 1])
            {
                suf[i] = height[i];
            }
            else
            {
                suf[i] = suf[i + 1];
            }
        }
        int ans = 0;
        int slow = 0; 
        int fast = 0;
        while (fast < n)
        {
            if (height[slow] <= height[fast] || suf[fast] == height[fast])
            {
                slow = fast;
            }
            else
            {
                ans += min(height[slow] - height[fast], suf[fast] - height[fast]);
            }
            fast++;
        }
        return ans;
    }
};

解法二（双指针）：

class Solution {
public:
    int trap(vector<int>& height) {

        int left = 0;
        int right = height.size()-1;


        int leftMax = 0;
        int rightMax = 0;


        int ans = 0;


        while(left < right)
        {

            if(height[left] < height[right])
            {

                if(height[left] >= leftMax)
                {
                    leftMax = height[left];
                }
                else
                {
                    ans += leftMax - height[left];
                }


                left++;
            }

            else
            {

                if(height[right] >= rightMax)
                {
                    rightMax = height[right];
                }
                else
                {
                    ans += rightMax - height[right];
                }


                right--;
            }
        }


        return ans;
    }
};

核心思想

这题的核心不是直接模拟水怎么流，而是先想清楚：某一个位置上方最多能存多少水。

对于下标 i，如果它上方能接水，那么这部分水一定同时被左边的某根柱子和右边的某根柱子挡住。

所以位置 i 的水面高度，取决于：

• 左边最高的柱子
• 右边最高的柱子
• 这两者中较矮的那一个

原因也很简单：如果左边最高柱子是 5，右边最高柱子是 3，那么水面最多只能到 3，再高就会从右边流走。

因此，位置 i 能接的水量就是：

min(左边最高柱子, 右边最高柱子) - height[i]

这就是这道题所有解法的根本依据。

公式推导

设：

leftMax[i] = max(height[0], height[1], ..., height[i])

表示从最左边到位置 i 为止的最高柱子。

再设：

rightMax[i] = max(height[i], height[i + 1], ..., height[n - 1])

表示从位置 i 到最右边的最高柱子。

对于位置 i：

• 水面不能高于 leftMax[i]，否则会从左边流走
• 水面不能高于 rightMax[i]，否则会从右边流走

所以水面高度一定是：

waterLevel[i] = min(leftMax[i], rightMax[i])

而位置 i 本身已经有高度为 height[i] 的柱子，所以真正能放水的高度是：

water[i] = waterLevel[i] - height[i]

代入得到：

water[i] = min(leftMax[i], rightMax[i]) - height[i]

由于每根柱子的宽度都是 1，所以高度差就是当前位置的水量。

最终答案为：

ans = sum(min(leftMax[i], rightMax[i]) - height[i])

注意，因为 leftMax[i] 和 rightMax[i] 都包含 height[i] 本身，所以：

min(leftMax[i], rightMax[i]) >= height[i]

因此每一项都不会是负数。

解法一：后缀最大值 + 左挡板扫描

第一份代码先从右往左预处理了 suf：

suf[i] = max(height[i], height[i + 1], ..., height[n - 1])

也就是位置 i 以及它右边的最高柱子。

然后从左往右扫描，用：

• slow 表示当前左侧挡板的位置
• fast 表示当前正在计算的位置

当扫描到 fast 时，如果当前位置不能成为新的边界，那么它上方能接的水就是：

min(height[slow], suf[fast]) - height[fast]

代码里写成：

ans += min(height[slow] - height[fast], suf[fast] - height[fast]);

这和下面这个式子等价：

ans += min(height[slow], suf[fast]) - height[fast];

只是把 height[fast] 提前减掉了。

什么时候要更新左挡板 slow 呢？

1. height[slow] <= height[fast]

说明 fast 位置的柱子已经不低于当前左挡板。

那么后面的位置如果要接水，用 fast 当左挡板一定不比原来的 slow 差，所以更新：

slow = fast;

2. suf[fast] == height[fast]

说明 fast 是从当前位置到结尾的最高柱子。

也就是说，fast 右边已经没有更高的柱子了。此时如果继续用旧的 slow 当左挡板，就会跨过一个右侧最高点，后面的接水区域应该重新开始计算。

所以也更新：

slow = fast;

解法二：双指针

第二份代码是空间更优的经典双指针写法。

它不提前保存完整的 leftMax 和 rightMax 数组，而是用两个变量动态维护：

• leftMax：当前左侧已经扫描过的最高柱子
• rightMax：当前右侧已经扫描过的最高柱子

双指针从两边向中间靠拢：

int left = 0;
int right = height.size() - 1;

每一轮比较：

if (height[left] < height[right])

如果左边更矮，就先结算左边。

原因是：当前右边已经存在一根比 height[left] 更高的柱子，右侧至少有挡板可以兜住当前位置的水。

所以位置 left 能不能接水，只看左边历史最高柱子 leftMax：

• 如果 height[left] >= leftMax，说明当前位置比左边所有柱子都高，不能接水，只能更新 leftMax
• 如果 height[left] < leftMax，说明左边有更高挡板，右边也有挡板，所以能接 leftMax - height[left]

然后移动：

left++;

右边同理。

当 height[left] >= height[right] 时，说明左边至少存在一根不低于 height[right] 的柱子，所以可以安全结算 right 位置。

此时：

• 如果 height[right] >= rightMax，更新右侧最高柱子
• 否则答案增加 rightMax - height[right]

然后移动：

right--;

双指针为什么正确

这里最关键的问题是：为什么每一轮只处理较矮的一侧？

假设当前：

height[left] < height[right]

这说明对于位置 left 来说，右边至少存在 height[right] 这根柱子作为右挡板。

因此，位置 left 缺的不是右挡板，而是要看左边是否已经出现过更高的柱子。

也就是：

• 如果 leftMax <= height[left]，当前位置左边没有更高挡板，接水量为 0
• 如果 leftMax > height[left]，当前位置左边有挡板，右边也有挡板，接水量为 leftMax - height[left]

所以当左边当前高度更低时，left 位置的水量已经可以确定，不需要再等中间未知的柱子。

如果当前：

height[left] >= height[right]

逻辑完全对称。

此时对于位置 right 来说，左边已经有 height[left] 这根柱子作为左挡板。
所以 right 位置能不能接水，只取决于右边历史最高柱子 rightMax。

这就是双指针每次移动较矮一侧的原因。

正确性证明

我们证明：双指针算法每次结算一个位置时，计算出的水量都是正确的。

归纳基

初始时：

• left = 0
• right = n - 1
• leftMax = 0
• rightMax = 0

由于题目中 height[i] >= 0，用 0 作为初始最高柱子不会影响答案。

此时还没有任何位置被结算，结论显然成立。

归纳假设

假设某一轮循环开始前：

• left 左边的位置都已经被正确结算
• right 右边的位置都已经被正确结算
• leftMax 是左侧已经扫描过区域的最大高度
• rightMax 是右侧已经扫描过区域的最大高度

归纳推导

如果 height[left] < height[right]，那么右侧至少存在一根高度为 height[right] 的柱子。

因此 left 位置的右挡板已经存在。

此时：

• 如果 height[left] >= leftMax，当前位置是新的左侧最高柱子，水量为 0
• 如果 height[left] < leftMax，左侧有 leftMax 作为左挡板，右侧有当前 right 作为右挡板，水量为 leftMax - height[left]

所以算法结算 left 是正确的。

结算后，left++，并且 leftMax 被正确维护，归纳假设继续成立。

如果 height[left] >= height[right]，同理可以证明 right 位置的水量可以被正确结算：

• 如果 height[right] >= rightMax，当前位置是新的右侧最高柱子，水量为 0
• 如果 height[right] < rightMax，右侧有 rightMax 作为右挡板，左侧有当前 left 作为左挡板，水量为 rightMax - height[right]

结算后，right--，并且 rightMax 被正确维护。

每一轮循环都会正确结算一个位置，直到 left >= right，所有位置都被处理完。

因此双指针算法正确。

复杂度分析

解法一

• 预处理后缀最大值数组需要 O(n)
• 从左到右扫描需要 O(n)
• 总时间复杂度：O(n)
• 额外空间复杂度：O(n)

解法二

• left 和 right 每次循环都会移动一个
• 每个位置最多被处理一次
• 总时间复杂度：O(n)
• 只使用常数个变量
• 额外空间复杂度：O(1)

所以一般更推荐解法二：双指针。