LeetCode 407. 接雨水 II
题目描述
题意分析
每个格子的宽和长都是 1，积水体积就是水面高度减去地面高度。水可以沿上下左右绕行到地图边缘，因此一个格子能存多少水，取决于通向任意边界的泄水路径，不能只看同一行的左右高墙。
解法：小根堆维护外圈最低边界
核心思路
[!blue]
沿一条路径向外排水，需要越过这条路径上的最高地面；在所有通往外边界的路径中，最高地面最低的那条决定泄水高度。与其为每个格子分别寻找出口，不如从所有外边界一起向内扩展，先处理最低的出口。
小根堆中的每项保存坐标和有效高度
H：它是这个位置已经确定的泄水高度，也是向内扩展时传递的水位。所有外边界都能直接向外排水，所以它们的有效高度就是自身地面高度，且不计积水。弹出有效高度最小的格子，设一个未访问邻居的地面高度为
h。若h < H，邻居可以蓄水到H，新增水量为H - h，再以水面高度H向内扩展；若h >= H，邻居自身就是更高的阻挡，不接水，之后传递高度h。合起来，新增水量是max(0, H - h)，入堆的有效高度是max(H, h)。为什么第一次发现邻居就能确定水位？此前弹出的格子都检查过四周，所以在本次弹出之前，未访问区域通向外界的路径必然经过堆中的某个格子。本次弹出的
H是堆内最小值，其他出口不会提供低于H的泄水高度；路径又不可能低于邻居自身的地面h。而经过当前格子的路径恰好达到max(H, h)，因此已经最优，可以立刻标记访问并结算一次。
解题步骤
- 行数或列数小于 3 时没有内部格子，返回 0。
- 将四条外边界按原始地面高度加入小根堆并标记访问，角点只加入一次。
- 弹出有效高度最小的格子，枚举上下左右四个邻居，跳过越界或已访问的位置。
- 对未访问邻居立即标记，若其地面低于当前有效高度，就把高度差计入答案。
- 取当前有效高度与邻居地面高度的较大值，让邻居携带这个高度入堆。
- 堆空时所有格子都已处理，返回累计水量。
代码实现
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)$，用于访问数组和小根堆。
关键点总结
[!green]
- 一条外流路径由最高地面限制，多条路径中选限制最低的出口。
- 堆维护的是已经确定的有效水位，每次用最低水位向内扩展。
- 低洼地填满后，其水面继续承担边界作用，所以邻居以
max(H, h)入堆。- 最低水位优先保证邻居首次被发现时即可定值，入堆时标记使每个格子只计水一次。
易错点总结
[!yellow]
- 分别按行或列套用一维算法，会忽略水绕行到其他方向出口的可能。
- 邻居按原始高度入堆，会丢失已经形成的水面高度并低估后续水量。
- 出堆时才标记访问，可能让同一格从多个方向重复入堆和重复计水。
- 只放入部分外边界会遗漏泄水出口；当前一次定值的写法也不能直接改用普通队列或大根堆。
- 入堆高度与积水量不是同一个量：前者取
max(H, h)，后者取max(0, H - h)。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 42. 接雨水 | 困难 | 一维只需左右边界，本题四周都可能漏水，需要从最低外边界逐步向内扩展。 |
| 778. 水位上升的泳池中游泳 | 困难 | 同样用最小堆维护不断抬高的可达水位，原题求抵达终点所需的最低水位。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！