时间轴

2025-10-03

init

题目：

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高度)（水填满了之后，它的高度相当于水面）。把邻居加入堆。
    • 不断重复，直到堆为空。

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

举个例子

1
2
3
4
5
6
[
  [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。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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;
  }
};