LeetCode 407. 接雨水 II
目录
题目描述
题意分析
给定一个
m × n的整数矩阵heightMap，每个格子表示该位置柱子的高度。下雨之后，水可以在柱子围成的凹陷里积起来，但只要存在一条从某格出发、经过四连通相邻格子、最终走到矩阵边界的路径，且路径上所有格子的高度都不高于当前水位，水就会顺着这条路径流走。要求返回整个矩阵最多能积多少单位的水。关键在于把「二维接水」和一维的 42 题区分开。一维里每个位置的水位是
min(左边最高, 右边最高)，因为水只能往左右两个方向逃逸。二维里水有四个方向可以逃，而且逃逸路径可以绕行、可以拐弯，所以某一格的水位并不由它所在行或所在列的极值决定。正确的直觉是木桶的最短板：把整个矩阵想象成一个不规则的容器，某个格子的水位等于「从该格走到矩阵外部的所有路径中，每条路径上最高障碍的最小值」。换句话说，水会沿着最容易溢出的那条路走，而那条路的瓶颈就是整个包围圈的最短板。因此二维接水必须从外向内逐层确定水位：先知道外壳有多高，才能知道里面能兜住多少水。
约束里的信号：矩阵边界上的格子永远存不住水，因为它们直接与外界相邻；只要行数或列数小于 3，就不存在被四面包围的内部格子，答案必然是
0。此外高度可以为0，也可以出现大片等高的平台，等高时不产生新的水量但仍会向内传递水位。
解法：小根堆维护外圈最低边界
核心思路
二维地形不能逐行套一维接雨水，因为水可能从其他方向流出。一个格子的最终水位由它到边界的所有路径中「最大高度最小」的那条路径决定，这是一个从外向内的瓶颈最短路问题。
将全部边界格子放入小根堆，它们构成初始外壳。每次弹出有效高度最低的外壳格子
cur，处理未访问邻居：
- 邻居更低时，可接水
cur.height - neighborHeight；- 邻居加入新外壳后的有效高度为
max(cur.height, neighborHeight)。核心不变量是：堆顶有效高度单调不减。新格子的有效高度不会低于当前堆顶，因此第一次把格子纳入外壳时，已找到了它通往边界的最低瓶颈；以后不可能出现更低的排水口。于是每格只需访问和结算一次。这与 Dijkstra 的贪心选择同构，只是路径代价由求和变成取沿途最大值。
解题步骤
- 行数或列数小于 3 时没有内部格子，返回 0。
- 将四条边加入小根堆并立即标记访问，避免角点重复入堆。
- 弹出当前最低外壳，枚举四邻域；越界或已访问的格子跳过。
- 邻居先标记访问，再累加
max(0, cur.height - neighborHeight)。- 以
max(cur.height, neighborHeight)作为邻居的有效高度入堆，继续向内推进。样例中高度为 1、2、2 的三个洼地都被外壳水位 3 限制，分别接 2、1、1 单位水，总量为 4。若只按行计算会忽略列方向的泄水路径。
代码实现
import java.util.PriorityQueue;
class Solution {
private static final int[] ROW_DIRS = {1, -1, 0, 0};
private static final int[] COL_DIRS = {0, 0, 1, -1};
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length;
int n = heightMap[0].length;
if (m < 3 || n < 3) {
return 0;
}
boolean[][] visited = new boolean[m][n];
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
for (int row = 0; row < m; row++) {
addBoundary(heightMap, visited, heap, row, 0);
addBoundary(heightMap, visited, heap, row, n - 1);
}
for (int col = 1; col < n - 1; col++) {
addBoundary(heightMap, visited, heap, 0, col);
addBoundary(heightMap, visited, heap, m - 1, col);
}
int ans = 0;
while (!heap.isEmpty()) {
int[] cur = heap.poll();
for (int dir = 0; dir < 4; dir++) {
int nextRow = cur[0] + ROW_DIRS[dir];
int nextCol = cur[1] + COL_DIRS[dir];
if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol]) {
continue;
}
visited[nextRow][nextCol] = true;
// 当前最低外壳决定邻居最多能接到多高。
if (heightMap[nextRow][nextCol] < cur[2]) {
ans += cur[2] - heightMap[nextRow][nextCol];
}
heap.offer(new int[] {nextRow, nextCol, Math.max(heightMap[nextRow][nextCol], cur[2])});
}
}
return ans;
}
private void addBoundary(int[][] heightMap, boolean[][] visited, PriorityQueue<int[]> heap, int row, int col) {
if (visited[row][col]) {
return;
}
visited[row][col] = true;
heap.offer(new int[] {row, col, heightMap[row][col]});
}
}
import "container/heap"
func trapRainWater(heightMap [][]int) int {
m, n := len(heightMap), len(heightMap[0])
if m < 3 || n < 3 {
return 0
}
visited := make([][]bool, m)
for row := 0; row < m; row++ {
visited[row] = make([]bool, n)
}
h := &cellHeap{}
for row := 0; row < m; row++ {
addRainBoundary(heightMap, visited, h, row, 0)
addRainBoundary(heightMap, visited, h, row, n-1)
}
for col := 1; col < n-1; col++ {
addRainBoundary(heightMap, visited, h, 0, col)
addRainBoundary(heightMap, visited, h, m-1, col)
}
rowDirs := []int{1, -1, 0, 0}
colDirs := []int{0, 0, 1, -1}
ans := 0
for h.Len() > 0 {
cur := heap.Pop(h).(cell)
for dir := 0; dir < 4; dir++ {
nextRow := cur.row + rowDirs[dir]
nextCol := cur.col + colDirs[dir]
if nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol] {
continue
}
visited[nextRow][nextCol] = true
// 当前最低外壳决定邻居最多能接到多高。
if heightMap[nextRow][nextCol] < cur.height {
ans += cur.height - heightMap[nextRow][nextCol]
}
heap.Push(h, cell{row: nextRow, col: nextCol, height: max(heightMap[nextRow][nextCol], cur.height)})
}
}
return ans
}
type cell struct {
row int
col int
height int
}
type cellHeap []cell
func (h cellHeap) Len() int {
return len(h)
}
func (h cellHeap) Less(i int, j int) bool {
return h[i].height < h[j].height
}
func (h cellHeap) Swap(i int, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *cellHeap) Push(value any) {
*h = append(*h, value.(cell))
}
func (h *cellHeap) Pop() any {
old := *h
value := old[len(old)-1]
*h = old[:len(old)-1]
return value
}
func addRainBoundary(heightMap [][]int, visited [][]bool, h *cellHeap, row int, col int) {
if visited[row][col] {
return
}
visited[row][col] = true
heap.Push(h, cell{row: row, col: col, height: heightMap[row][col]})
}
func max(first int, second int) int {
if first > second {
return first
}
return second
}
复杂度分析
- 时间复杂度：$O(mn \log(mn))$，每个格子至多入堆、出堆一次。
- 空间复杂度：$O(mn)$，用于访问数组和小根堆。
关键点总结
- 二维水位由通向边界的最低瓶颈决定，必须从完整外边界向内扩展。
- 小根堆保证先确定最低外壳，与 Dijkstra 的贪心选择同构。
- 邻居入堆的是有效水位
max(自身高度, 外壳高度)，不是原始高度。visited必须在入堆时设置，确保每格只结算一次。
易错点总结
- 分别按行套用一维算法会忽略其他方向的泄水路径，样例会从 4 错算成 7。
- 邻居按原始高度入堆，会丢失已经形成的水面高度并低估后续水量。
- 出堆时才标记访问，可能让同一格从多个方向重复入堆和重复计水。
- 漏掉任意一条外边界，或误用普通队列、大根堆，都会破坏「最低外壳优先」的不变量。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 42. 接雨水 | 困难 | 一维前后缀最大值与双指针 |
| 778. 水位上升的泳池中游泳 | 困难 | 最小化路径上的最大高度 |
| 1631. 最小体力消耗路径 | 中等 | 最小化相邻高度差的瓶颈路 |
| 417. 太平洋大西洋水流问题 | 中等 | 从边界反向搜索求可达交集 |
| 994. 腐烂的橘子 | 中等 | 多源 BFS 按层扩散计时 |
| 743. 网络延迟时间 | 中等 | 堆优化 Dijkstra 求单源最短路 |
| 200. 岛屿数量 | 中等 | 网格连通块的遍历与标记 |