leetcode每日一题 P407 接雨水II

---

时间轴

时间轴

2025-10-03

init

小顶堆，BFS

---

题目：

P407 接雨水II

https://leetcode.cn/problems/trapping-rain-water-ii/description/?envType=daily-question&envId=2025-10-03

• 边界格子永远不能存水因为水会从边界流走，所以水池的边界就是矩阵的四周。

• 从最矮的边界开始填充类似「木桶效应」，水位由最低的边界决定。因此我们需要 动态维护当前最低的边界高度。

• 算法步骤（小根堆 + BFS）

  • 把 所有边界格子（四周一圈）放进 最小堆（优先队列，按高度从小到大排序），并标记为已访问。
  • 每次从堆里弹出一个当前最低的格子，记作 cell。
  • 扫描它的 4 个方向的邻居：
    • 如果邻居没访问过：若邻居高度 < cell 的高度，说明这里能积水，积水量是 cell 高度 - 邻居高度。更新邻居的「有效高度」为 max(邻居高度, cell 高度)（水填满了之后，它的高度相当于水面）。把邻居加入堆。
  • 不断重复，直到堆为空。

这样，整个算法就相当于「从最矮的边界往里灌水」。

举个例子

[
  [5,5,5,5],
  [5,1,1,5],
  [5,1,1,5],
  [5,5,5,5]
]

外圈高度全是 5，中间是 1。从边界出发，堆里最低高度是 5。处理到中间格子时，发现高度 1，比边界水位 5 低 → 能装 4 个水。每个内部格子装 4，最后得到 4*4=16。

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

using std::priority_queue;
using std::tuple;
using std::vector;

typedef priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >,
                       std::greater<tuple<int, int, int> > >
        min_heap;
class Solution {
    public:
        int trapRainWater(vector<vector<int> > &heightMap)
        {
                int m = heightMap.size();
                int n = heightMap[0].size();
                int res = 0;
                min_heap pq;

                vector<vector<bool> > visit(m, vector<bool>(n, false));

                if (m <= 2 || n <= 2) {
                        return 0;
                }
                for (int i = 0; i < m; ++i) {
                        for (int j = 0; j < n; ++j) {
                                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                                        pq.push({ heightMap[i][j], i, j });
                                        visit[i][j] = true;
                                }
                        }
                }

                int dirs[] = { -1, 0, 1, 0, -1 };
                while (!pq.empty()) {
                        auto [h, x, y] = pq.top();
                        pq.pop();
                        // 遍历堆顶的上下左右
                        for (int k = 0; k < 4; ++k) {
                                int nx = x + dirs[k];
                                int ny = y + dirs[k + 1];
                                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                                        if (heightMap[nx][ny] < h) {
                                                res += h - heightMap[nx][ny];
                                        }
                                        visit[nx][ny] = true;
                                        pq.push({ std::max(heightMap[nx][ny], h), nx, ny });
                                }
                        }
                }

                return res;
        }
};