🌊 问题描述

给定一个 m x n 的二维矩阵 heightMap，其中每个元素表示该位置的高度。计算下雨后这个地形能够捕获多少雨水。

示例：

1
2
3
4
5
6
7
输入：heightMap = [
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]
输出：4
解释：下雨后，雨水被捕获在两个低洼区域，总容量为4。

🔑 核心思路：从边界向内收缩的木桶原理

直观理解

想象这个二维矩阵是一个盆地，雨水会从四周边界流出。只有当四周有足够高的”围墙”时，雨水才能被积攒在内部。

这就像是一个二维的木桶效应：一个位置的积水高度取决于它到边界的所有路径中，路径上最高点的最小值。

关键洞察

  1. 边界决定论：只有边界上的单元格不会积水（水会流出）
  2. 最小最大值原理：内部单元格的积水高度由从边界到该单元格的所有路径中，路径上最大高度的最小值决定

🧠 算法详解：优先队列+BFS

📊 初始化阶段

1
2
3
4
5
6
7
8
9
10
// 处理特殊情况
if (heightMap.length <= 2 || heightMap[0].length <= 2) {
    return 0;
}

int m = heightMap.length;
int n = heightMap[0].length;
boolean[][] visit = new boolean[m][n]; // 访问标记数组
// 使用最小堆，按高度排序
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

🚀 边界处理

将所有边界单元格加入优先队列：

1
2
3
4
5
6
7
8
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.offer(new int[]{i * n + j, heightMap[i][j]});
            visit[i][j] = true; // 标记已访问
        }
    }
}

为什么从边界开始？ 因为边界是雨水的”出口”，积水高度不可能超过边界高度。

🔄 核心处理循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int res = 0; // 总积水量
int[] dirs = {-1, 0, 1, 0, -1}; // 方向数组：上、右、下、左

while (!pq.isEmpty()) {
    int[] curr = pq.poll(); // 取出当前最小高度的单元格
    for (int k = 0; k < 4; ++k) { // 检查四个方向
        int nx = curr[0] / n + dirs[k];
        int ny = curr[0] % n + dirs[k + 1];
        
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
            // 如果当前高度大于相邻单元格高度，可以积水
            if (curr[1] > heightMap[nx][ny]) {
                res += curr[1] - heightMap[nx][ny];
            }
            // 将相邻单元格加入队列，高度取最大值
            pq.offer(new int[]{nx * n + ny, Math.max(heightMap[nx][ny], curr[1])});
            visit[nx][ny] = true; // 标记已访问
        }
    }
}
return res;

💡 算法精髓

初始状态：

1
2
3
4
5
6
7
8
┌─────────┐
│B B B B B│
│B I I I B│
│B I I I B│
│B I I I B│
│B B B B B│
└─────────┘
B: 边界单元格 I: 内部单元格

处理过程：
总是从最低的边界开始扩展，逐步向内处理

  1. 最小堆保证：总是先处理当前最低的边界点
  2. 高度传播：相邻单元格的有效高度 = max(当前高度, 自身高度)
  3. 积水计算：当有效高度 > 自身高度时，差值即为积水量

🧠 为什么这个算法有效？

木桶原理的数学表达

对于每个内部单元格 (i, j)，其积水高度为：

1
F(i,j) = min{ max{ height along path } for all paths from boundary to (i,j) }

算法通过优先队列动态计算了这个最小值：

  • 每次取出最小高度的单元格，意味着我们找到了到达该点的”最低门槛”
  • 通过这个单元格扩展，我们确保相邻单元格的积水高度不会低于当前门槛

现实世界类比

想象雨水从盆地四周的最低点先开始溢出，然后逐渐向内漫延。算法模拟的正是这个过程：

  1. 水从最矮的边界处先开始流入内部
  2. 内部低洼处先积水，形成”小水坑”
  3. 随着水位上升，这些小水坑连成一片
  4. 最终整个盆地的积水达到平衡状态

⏱ 复杂度分析

  • 时间复杂度：O(mn log(mn))
    • 每个单元格入堆一次，堆操作时间复杂度为 O(log(mn))
  • 空间复杂度：O(mn)
    • 用于存储访问标记和优先队列

🎯 总结

这个算法巧妙地将二维积水问题转化为基于优先队列的BFS遍历，核心在于：

  1. 从边界开始：边界决定积水上限
  2. 使用最小堆：确保总是处理当前最低的点
  3. 动态更新高度：传播当前最大的有效高度
  4. 累加差值：计算实际积水量

这种思路不仅适用于接雨水问题，还可以推广到其他类似的扩散、填充类问题中，是一种很值得掌握的算法模式。

📝 完整代码实现

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
class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length <= 2 || heightMap[0].length <= 2) {
            return 0;
        }
        int m = heightMap.length;
        int n = heightMap[0].length;
        boolean[][] visit = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        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.offer(new int[]{i * n + j, heightMap[i][j]});
                    visit[i][j] = true;
                }
            }
        }
        
        int res = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            for (int k = 0; k < 4; ++k) {
                int nx = curr[0] / n + dirs[k];
                int ny = curr[0] % n + dirs[k + 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                    if (curr[1] > heightMap[nx][ny]) {
                        res += curr[1] - heightMap[nx][ny];
                    }
                    pq.offer(new int[]{nx * n + ny, Math.max(heightMap[nx][ny], curr[1])});
                    visit[nx][ny] = true;
                }
            }
        }
        return res;
    }
}