LeetCode42. [H]接雨水（动态规划、单调栈、双指针*）

‍

LeetCode42.接雨水

思路

对于每一个柱子，他所能接的雨水就是左边最高的柱子和右边最高的柱子小的那一个再减去自己的高度。
既：min(leftMax[i],rightMax[i])−height[i]

解题方法

动态规划

官方题解（截取）：

创建两个长度为 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] 。遍历每个下标位置即可得到能接的雨水总量。

代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        //获取每个元素左边的最大值（从左到右遍历）
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }
        //获取每个元素右边的最大值（从右到左遍历）
        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

可优化：

1. 数组中有许多重复的leftMax和rightMax

复杂度分析

• 时间复杂度：O(n),其中 n 是数组 height 的长度，获取leftMax、rightMax和计算结果需遍历三次数组，故O(3n)=O(n);
• 空间复杂度：O(n)，其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax，故O(2n)=O(n)。

单调栈

官方题解（截取）：

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。

• 左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，既left top i,则一定有 height[left]≥height[top] (因为只有后一个元素小于等于栈顶元素才会入栈)。如果 height[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，高度是 min(height[left],height[i])−height[top] ，根据宽度和高度即可计算得到该区域能接的雨水量。

代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        //遍历每一个元素
        for (int i = 0; i < n; ++i) {
            //如果栈中有元素，且当前的柱子高于栈顶，既满足 left<=top<i
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                //防止栈中只有一个元素
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            //i<=top 入栈
            stk.push(i);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 height 的长度，while部分每个元素只会入栈/出栈一次，故为O（n）。
• 空间复杂度：O(n)，其中 n 是数组 height 的长度，空间复杂度主要取决于栈空间，栈的大小不会超过 n。

双指针（*）

个人理解

对于每一个柱子，我们只需要知道左边最大值（以下称为leftMax）和右侧最大值（以下称为rightMax），即可计算当前柱子可存放水的容量，既min(leftMax,rightMax)-currHeight。

代码：

我们不必知道两个边界的较大者是谁，只要知道较小者是谁就可以了
初始化 left = 0, right = n-1, leftMax = 0, rightMax = 0

• 对于位置 left 来说, leftMax 是其真正的左侧最大值, 而 rightMax 不是其真正的右侧最大值,因为区间（left, right）的值还没有遍历，但可以确定的是，left的rightMax一定>= right的rightmax
• 同理，对于位置 right 来说, rightMax 是真的右侧最大值,而 leftMax 不是其真正的左侧最大值，因为区间（left, right）的值还没有遍历，但仍然可以确定，right的leftMax一定>=left的leftMax

以位置left为例：
    1. 使用 height[left] 和 height[right] 得到 leftMax和rightMax
    2. 若 leftMax < rightMax, 则说明对于left 来说,
    leftMax 一定小于其右侧真正意义上的最大值，
    因为leftMax<[right,n]的局部最大值, 更比不过包含（left，right）区间的真正的rightMax
    而我们计算当前柱子的充水量只需要知道较小的边界即可，所以冲水量为leftMax - height[left]
    3. 类似地处理 rightMax >= leftMax 的情况

class Solution {
public:
    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 (leftMax < rightMax)
            {
                ans += leftMax - height[left];
                ++left;
            }
            else
            {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
• 空间复杂度：O(1)。只需要使用常数的额外空间。

对于官方题解的理解

动态规划的做法中，需要维护两个数组 leftMax 和 rightMax，因此空间复杂度是 O(n)。是否可以将空间复杂度降到 O(1)？

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

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

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

使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；

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

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

官方题解中​​height[left]<height[right]，则必有 leftMax<rightMax​​很不好理解。（对于当时的笔者）
先贴上官方代码：

class Solution {
public:
    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;
    }
};

其实，我们每一次移动的都是left和right，都是当前已遍历元素的较小侧，

以 height=[0,1,0,2,1,0,1,3,2,1,2,1]为例：

1. 初始循环时，height[left]<height[right]为tue，此时执行left++，那此时也就代表leftMax<rightMax，而我们只移动小的指针，也就代表height[right]其实就是此时的rightMax
2. 第1次循环时，height[left]<height[right]为false,此时leftmax和rightmax相等，我们移动左边指针，此时的height[left]其实就是leftMax。
3. 再看第2次循环，left不断++，right没有发生变化，此时的height[right]仍然是rightMax，直到下一次切换移动的指针，既第4次循环，此时leftMax就是height[left]，rightMax就是height[right] ，已经满足了leftMax>righMax（因为要满足height[left]<height[right]为false，才会开始执行r--）。

总结：

• 从初始开始，每次对指针的切换时就已经提前知道了当前已遍历元素的最高柱子

• 以操作left为例，主要目的为：

  1. 寻找（leftMax,rightMax）区间中更高的柱子，同时计算充水量
  2. 寻找大于rightMax的边，也就是新的最高柱子，寻找较小侧元素成为最高柱子的可能。
  3. 当发现height[left]>height[right]=rightMax,切换操作的指针，此时的left已经不会移动，此时的rightMax，小于leftMax，所以后续可能比leftMax大的柱子只能从新的height[right]中出现，依次循环
• 所以在较小侧移动的时候，在需要切换操作的指针（较小边）就已经满足了该指针所对应的Max一定小于另一侧的Max，新的最高柱子只能从较小侧新遍历的柱子中出现。

笔者的逻辑可能有些难以理解，以下是GPT的总结：

📌 指针切换与 leftMax < rightMax 的关系详解
在初始循环中，height[left] < height[right] 成立，因此会执行 left++。
此时可以认为 leftMax < rightMax，因为我们总是移动值较小的一边，
而另一边（此处是 right）的值就是当前的 rightMax，可以信任它是足够高的挡板。

第 1 次循环后，当 height[left] >= height[right]，进入 else 分支，开始移动 right。
此时 leftMax 与 rightMax 相等，left 暂时不再移动，height[left] 就是当前的 leftMax。

继续第 2 次循环后，left 不断右移，right 未发生变化，
所以 height[right] 始终等于当前的 rightMax，
一直到某一时刻再度切换指针（即 height[left] < height[right]），
此时的 leftMax 就是 height[left]，rightMax 是 height[right]，
满足了 leftMax > rightMax，因此开始向左移动 right。

🧠 总结逻辑：
从最开始，每次切换移动的指针之前，我们就已经知道当前两侧的最大值，即 leftMax 和 rightMax。

以移动 left 为例，这一步的本质是：

在当前 leftMax < rightMax 的前提下，寻找左侧区域可以装水的位置；

寻找下一个可能大于 rightMax 的柱子（即新的最大值）；

一旦发现 height[left] >= height[right]，就会切换指针，进入 right-- 的分支。

切换指针的时机，其实就意味着：

当前较小侧的 Max（即我们一直移动的那一侧）已经大于等于另一侧的 Max；

后续再出现的新高柱子，只可能出现在另一侧尚未遍历的区域。

所以：

每当我们决定移动较矮的那一边时，它的最大值一定小于等于另一边的最大值。 这是算法可以成立的核心，也是计算雨水量时可以“信任较矮一边”的前提。

结语

本文基于笔者的个人笔记修改而来，内容有着较强的个人色彩（适合笔者理解），可能不适用于他人，如部分内容有误，恳请斧正。 在学习接雨水的双指针解法过程中，我理解了leftMax和rightMax的作用，可能因为笔者愚钝，在翻遍评论区后也无法理解为何height[left]<height[right]，则必有 leftMax<rightMax​，直到自己手动计算了几个输入，才明白为何如此，这次经历让我深刻明白了一个道理，无论是算法还是开发中编写的其他代码，都应该是在保证达成目的、平衡时空效率的前提下，尽量通俗易懂，减少他人的理解成本。

参考

LeetCode官方题解

这篇文章介绍了LeetCode第42题“接雨水”的三种解法：动态规划、单调栈和双指针。题目要求在给定柱子高度的数组中，计算能够接住的雨水总量。核心思路是对于每个柱子，其接水量取决于左右两侧最高柱子的较小值减去自身高度。
动态规划解法通过预处理左右最大高度数组，然后计算每个位置的接水量，时间复杂度和空间复杂度均为O(n)。单调栈解法利用栈结构维护递减序列，遇到更高柱子时计算接水区域，时间复杂度O(n)，空间复杂度O(n)。文章还提到双指针解法（未展开），可在O(1)空间完成。
三种方法均围绕“左右边界最小值决定水位”的核心思想，提供了不同时空复杂度的实现方案，适用于不同场景需求。