接雨水专题 (Trapping Rain Water)¶

接雨水（Trapping Rain Water）是算法面试与程序设计竞赛中的传世经典。它不仅涵盖了基础的数组扫描与几何分片，更深刻映射了木桶短板原理、对撞双指针单调性、单调栈凹槽消除以及高维网格堆收缩（Dijkstra 思想）等核心算法设计范式。

1. 物理本质与建模思想 (Physical Modeling)¶

在重力场的作用下，水往低处流。水体之所以能被截留蓄积，是因为在其流向外部逃逸的路径上存在“高于地表”的屏障。

1.1 纵向切片：柱子单位法 (Vertical Slicing)¶

在一维高度图（柱状地形）中，若以每个柱子位置 \(i\) 为考察单元：

该位置的水面最高能涨到多高？取决于它左侧的所有屏障最高有多高（\(\max_{0 \le k \le i} h[k]\)）与右侧的所有屏障最高有多高（\(\max_{i \le k < n} h[k]\)）的较小值（短板效应）；
扣除该柱子自身的地表高度 \(h[i]\)，即为位置 \(i\) 的净积水量：

\[ \text{water}[i] = \max\left(0, \min\left(\max_{0 \le k \le i} h[k], \max_{i \le k < n} h[k]\right) - h[i]\right) \]

总积水量即为各纵向柱子积水的代数和：

\[ V = \sum_{i=0}^{n-1} \text{water}[i] \]

1.2 横向切片：水层分层法 (Horizontal Slicing)¶

若从水流聚集的几何“凹槽”形态切入：

每当高度发生“下降后又上升”，便形成了一个天然的容水凹槽；
我们可以将凹槽自底向上按水平层切片计算：以某个相对较低的柱子为底，以其左右两侧第一个高于它的柱子为壁，累加每一层的储水量：

\[ \Delta V = (\min(h_{\text{left}}, h_{\text{right}}) - h_{\text{bottom}}) \times (idx_{\text{right}} - idx_{\text{left}} - 1) \]

这两种切片视角分别诞生了一维接雨水最精妙的双指针法与单调栈法。

2. 一维接雨水：三大经典解法深度全解 (LeetCode 42)¶

2.1 解法一：前后缀最值分解（动态规划）¶

最直观的方法是直接落实纵向切片公式。对于每个下标 \(i\)，我们需要快速知道它的左侧最大值与右侧最大值。

预处理前缀最大值数组 \(left\_max[i] = \max(left\_max[i-1], h[i])\)；
预处理后缀最大值数组 \(right\_max[i] = \max(right\_max[i+1], h[i])\)；
遍历数组，累计 \(\min(left\_max[i], right\_max[i]) - h[i]\)。
时间复杂度：\(\mathcal{O}(N)\)，需要进行三次线性遍历。
空间复杂度：\(\mathcal{O}(N)\)，需要两个辅助数组。

#include <vector>
#include <algorithm>

int trap_dp(const std::vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;

    std::vector<int> left_max(n), right_max(n);
    left_max[0] = height[0];
    for (int i = 1; i < n; ++i) {
        left_max[i] = std::max(left_max[i - 1], height[i]);
    }

    right_max[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        right_max[i] = std::max(right_max[i + 1], height[i]);
    }

    int total_water = 0;
    for (int i = 0; i < n; ++i) {
        total_water += std::min(left_max[i], right_max[i]) - height[i];
    }
    return total_water;
}

2.2 解法二：对撞双指针（空间极致优化 \(\mathcal{O}(1)\)）¶

解法一中，我们为了知道“左边最大和右边最大中的较小者”，保存了整条前后缀链。然而，木桶短板原理告诉我们：只要知道了较短的那一侧短板，另一侧只要比它更高，具体有多高根本不重要！

严格不变式证明 (Invariant Proof)¶

设首尾双指针 \(left = 0, right = n - 1\)，分别维护历史遇到的左侧最高高度 \(left\_max\) 和右侧最高高度 \(right\_max\)。

当 \(left\_max < right\_max\) 时：
对于当前的 \(left\) 而言，其左侧的最大值确凿无疑就是 \(left\_max\)；
其右侧的最大值是多少？由于右指针所在处的真实高度为 \(height[right]\)，且已知当前扫描到的 \(right\_max \ge height[right]\)，因此 \(left\) 右侧的最大值必定大于等于 \(right\_max\)；
因为 \(left\_max < right\_max\)，所以有：

\[ \min(left\_max, \text{右侧绝对最大值}) = left\_max \]
这意味着：\(left\) 处的短板已经被完全锁定为 \(left\_max\)！右边未来到底有多高，完全不会改变 \(left\) 处的水位！
于是我们可以立即安全地结算 \(left\) 处的蓄水：\(\text{water}[left] = left\_max - height[left]\)，然后将 \(left++\)。
对称地，当 \(left\_max \ge right\_max\) 时，短板必定在右侧，\(right\) 处的蓄水高度被 \(right\_max\) 锁定，直接结算并令 \(right--\)。

#include <vector>
#include <algorithm>

int trap_two_pointers(const std::vector<int>& height) {
    int n = height.size();
    if (n <= 2) return 0;

    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int total_water = 0;

    while (left < right) {
        left_max = std::max(left_max, height[left]);
        right_max = std::max(right_max, height[right]);

        if (left_max < right_max) {
            total_water += left_max - height[left];
            left++;
        } else {
            total_water += right_max - height[right];
            right--;
        }
    }
    return total_water;
}

时间复杂度：\(\mathcal{O}(N)\)，每个元素仅被访问一次。
空间复杂度：\(\mathcal{O}(1)\)，仅需常数级变量。

2.3 解法三：单调栈（横向切片与凹槽消除）¶

单调栈是落实横向切片法的核心武器。

维护一个存储下标的单调递减栈（栈底到栈顶高度单调递减）；
一旦当前柱子 \(height[i]\) 大于栈顶柱子的高度，说明在栈顶附近出现了一个局部低洼的凹槽（凹槽已被当前更高的柱子“堵住”）；
此时将凹槽底部弹出：
记录凹槽底部高度 \(h_{\text{bottom}} = height[\text{top}]\)；
弹出后，若栈为空，说明左侧无更高柱子阻挡，无法聚水，直接 break；
若栈非空，此时新的栈顶即为凹槽左边界 \(left\)，当前柱子 \(i\) 为右边界 \(right\)；
当前切片可容纳的水位差：\(\Delta h = \min(height[left], height[right]) - h_{\text{bottom}}\)；
当前切片凹槽跨度宽度：\(w = right - left - 1\)；
累加横向切面积水：\(\Delta V = \Delta h \times w\)；
重复检查栈顶，直到栈恢复单调递减性质。

#include <vector>
#include <stack>
#include <algorithm>

int trap_monotonic_stack(const std::vector<int>& height) {
    int n = height.size();
    std::stack<int> st; // 存储下标，维护高度单调递减
    int total_water = 0;

    for (int i = 0; i < n; ++i) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int bottom = st.top();
            st.pop();
            if (st.empty()) break; // 左侧无屏障

            int left = st.top();
            int right = i;
            int bounded_height = std::min(height[left], height[right]) - height[bottom];
            int width = right - left - 1;
            total_water += bounded_height * width;
        }
        st.push(i);
    }
    return total_water;
}

时间复杂度：\(\mathcal{O}(N)\)，每个下标最多入栈出栈各一次。
空间复杂度：\(\mathcal{O}(N)\)，栈的最大深度为 \(N\)。

2.4 核心辨析与解法对比¶

维度	前后缀分解 (DP)	对撞双指针 (Two Pointers)	单调栈 (Monotonic Stack)
几何切片视角	纵向切片（柱子单位累计）	纵向切片（短板锁定累计）	横向切片（凹槽水平层累计）
时间复杂度	\(\mathcal{O}(N)\)（三遍扫描）	\(\mathcal{O}(N)\)（一遍对撞）	\(\mathcal{O}(N)\)（单遍入出栈）
空间复杂度	\(\mathcal{O}(N)\)	\(\mathcal{O}(1)\) (最优)	\(\mathcal{O}(N)\)
适用延伸场景	离线固定数组	极其简练，常数极小	适合流式数据、查找凹凸极值

关联模型经典辨析¶

VS 盛最多水的容器 (LeetCode 11)：
LC 11 考察两根外围板围成的面积 \((r - l) \times \min(h[l], h[r])\)，中间的柱子不会阻断水流；对撞双指针移动较矮的一边，是因为若移动较高的一边，底边变短且高度至多为较矮者，面积单调不增。
LC 42 内部柱子会占位并阻隔水流，是纯正的重力积水。
VS 柱状图中最大的矩形 (LeetCode 84)：
LC 84 是寻找左右两侧第一个小于自身的柱子作为边界，需要维护单调递增栈；
LC 42 是寻找左右两侧第一个大于自身的柱子作为屏障，需要维护单调递减栈。

3. 二维接雨水：三维地形与最小堆收缩 (LeetCode 407)¶

3.1 物理建模：高维木桶短板¶

给定一个 \(M \times N\) 的非负整数二维高度矩阵 \(heightMap[m][n]\)。在二维平面上，水能够向上下左右四个方向逃逸。如果内部某点想要蓄水，水必须在四周所有通往外界边界的路径上都被阻挡。

对于网格中任意内部点 \((x, y)\)：

从 \((x, y)\) 逃逸到网格最外层边界的所有可能网格路径集合记为 \(\mathcal{P}_{(x, y) \to \partial \Omega}\)；
沿着某条逃逸路径 \(P\)，水溢出的最低水线由该路径上的最高山峰 \(\max_{(u, v) \in P} heightMap[u][v]\) 决定；
水会在阻碍最薄弱的路径溢出，因此最终蓄水后的水平面高度为所有可能逃逸路径中最高峰的最小值（Minimax 瓶颈路径）：

\[ \text{water\_level}(x, y) = \min_{P \in \mathcal{P}_{(x, y) \to \partial \Omega}} \left( \max_{(u, v) \in P} heightMap[u][v] \right) \]

其蓄水量为：

\[ \Delta V(x, y) = \max\left(0, \text{water\_level}(x, y) - heightMap[x][y]\right) \]

3.2 算法设计：优先队列 (Min-Heap) + 外围向内收缩 (类似 Dijkstra)¶

如何高效求出每个格子的 Minimax 逃逸水线？答案是：从小根堆中不断取出当前最外围边界的最低点（木桶的当前最短木板），向内部扩散收缩。这与单源最短路算法 Dijkstra 具有异曲同工之妙！

算法执行流程：¶

边界初始化：
最外层边界上的格子直接连通外界，其水面不可能高于自身海拔（积水量必为 0）；
将四周边界所有格子全部加入小根堆（按当前水面高度排序），并打上已访问标记 visited；
木桶短板弹出：
每次从小根堆弹出水面最低的格子 \((h, x, y)\)；
此时 \(h\) 就是该格子乃至其相邻未访问低洼邻居向外泄露的最矮瓶颈！
四邻居松弛与蓄水：
遍历 \((x, y)\) 的上下左右四个相邻格子 \((nx, ny)\)；
若 \((nx, ny)\) 未访问：
- 若 \(heightMap[nx][ny] < h\)，说明该邻居地表比出水口还低，邻居处必定能蓄积 \(h - heightMap[nx][ny]\) 的雨水！此时该邻居的水面也上涨为 \(h\)；
- 若 \(heightMap[nx][ny] \ge h\)，说明该邻居地表比出水口更高，它无法通过当前出口积水，自身成为更高的出水口，其水面就是其地表高度 \(heightMap[nx][ny]\)；
- 将邻居的水位统一标记为 \(\max(h, heightMap[nx][ny])\)，压入小根堆，并标记为已访问；
收敛：重复该过程，直到堆为空。

#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

class Solution {
public:
    int trapRainWater(std::vector<std::vector<int>>& heightMap) {
        int m = heightMap.size();
        if (m <= 2) return 0;
        int n = heightMap[0].size();
        if (n <= 2) return 0;

        // 小根堆：存储元组 (当前水面高度, x, y)
        using Cell = std::tuple<int, int, int>;
        std::priority_queue<Cell, std::vector<Cell>, std::greater<Cell>> pq;
        std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));

        // 1. 将外围四条边界入堆
        for (int i = 0; i < m; ++i) {
            pq.emplace(heightMap[i][0], i, 0);
            pq.emplace(heightMap[i][n - 1], i, n - 1);
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }
        for (int j = 1; j < n - 1; ++j) {
            pq.emplace(heightMap[0][j], 0, j);
            pq.emplace(heightMap[m - 1][j], m - 1, j);
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }

        int total_water = 0;
        const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 2. 最小堆由外向内收缩
        while (!pq.empty()) {
            auto [h, x, y] = pq.top();
            pq.pop();

            for (int d = 0; d < 4; ++d) {
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    // 若邻居高度低于当前水面，则邻居能积水
                    if (heightMap[nx][ny] < h) {
                        total_water += h - heightMap[nx][ny];
                    }
                    // 邻居入堆的新水位为 max(h, 自身地表高度)
                    pq.emplace(std::max(h, heightMap[nx][ny]), nx, ny);
                }
            }
        }
        return total_water;
    }
};

时间复杂度：每个格子入堆和出堆各一次，共 \(MN\) 个点，单次堆操作 \(\mathcal{O}(\log(MN))\)，总时间复杂度为 \(\mathcal{O}(MN \log(MN))\)。
空间复杂度：\(\mathcal{O}(MN)\)，用于访问标记数组与优先队列。

4. 进阶变种与动态雨水模型¶

4.1 倒水模拟 (LeetCode 755 - Pour Water)¶

接雨水是静态平衡态；而倒水问题则是重力流体力学动力学模拟。

规则：水滴落在位置 \(K\)。
优先向左流动：若左侧存在严格低于当前水位的低洼地带，水滴顺坡滑向左边能到达的最低位置（若有多个最低，停留在离 \(K\) 最近的低谷）；
若左侧无更低处，尝试向右流动寻找更低洼地带；
若左右两边都不存在更低处，则水滴就地停留在 \(K\) 并使该位置高度增加 1。
解法：单次模拟遍历寻找极小值点，单次倒水 \(\mathcal{O}(N)\)，模拟 \(V\) 滴水复杂度为 \(\mathcal{O}(V \cdot N)\)。

4.2 动态单点修改接雨水 (Dynamic Updates on Rain Water)¶

如果高度图会发生动态更新（例如支持单点修改高度 \(h[p] \leftarrow v\)），并要求多次高效查询全局接水总量：

静态方法重新计算需要 \(\mathcal{O}(N)\)，无法承受多轮查询；
线段树分治信息维护：
观察雨水全局形态：整个雨水轮廓是由全局最大值劈成左右两半；
在左半部分，水位完全由前缀最大值决定；在右半部分，水位完全由后缀最大值决定；
利用线段树维护区间最大值，以及在给定外部左边界高度 \(H\) 条件下的区间积水面积（类似历史最值线段树 / 兔队线段树），可以在 \(\mathcal{O}(\log^2 N)\) 内支持单点修改与全局雨水查询。

5. LeetCode 经典好题精选与题解提示¶

LeetCode 42 - 接雨水 (Trapping Rain Water) 困难
提示

一维接雨水基石。
- 推荐掌握对撞双指针（\(\mathcal{O}(1)\) 空间）与单调递减栈（横向凹槽消除）两种核心思维。
- 双指针法则：短板在那侧，就结算哪侧，因为另一侧更高已是不变的事实。
LeetCode 407 - 接雨水 II (Trapping Rain Water II) 困难
提示

二维网格木桶短板 + Dijkstra 思想。
- 构建四边边界点入小根堆；
- 每次贪心取出外围出水口水位最低的格子向内部松弛；
- 邻居未访问时，若比当前出水口矮则累加积水，更新新水位 \(\max(h, heightMap[nx][ny])\) 入堆。
LeetCode 11 - 盛最多水的容器 (Container With Most Water) 中等
提示

双指针贪心短板单调性。
- 左右指针从两端向中间逼近。
- 面积为 \((r - l) \times \min(h[l], h[r])\)。每次收缩较矮的那一侧指针，因为移动较高一侧不可能使面积增大。
LeetCode 84 - 柱状图中最大的矩形 (Largest Rectangle in Histogram) 困难
提示

单调递增栈经典标杆。
- 维护单调递增栈，在遇到更矮柱子时结算以栈顶柱子为高度的最大矩形面积。左右两侧添加高度为 0 的哨兵可极大简化边界处理。
LeetCode 755 - 倒水 (Pour Water) 中等
提示

重力流动优先级模拟。
- 优先向左滑落至能达到的最远局部最低谷；若无更低洼点则向右滑落；若左右都无法滑落则落点原地 \(+1\)。