LC 407. 接雨水 II
题目描述
这是 LeetCode 上的 407. 接雨水 II ,难度为 困难。
给你一个 $m x n$ 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
示例 1:
1 |
|
示例 2:1
2
3输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10
提示:
- m == heightMap.length
- n == heightMap[i].length
- 1 <= m, n <= 200
- $0 <= heightMap[i][j] <= 2 * 10^4$
Dijkstra 变形 + 优先队列(堆)
首先,最外层的一圈(边界)是不会接到任何雨水的(会从边界流出)。
我们定义从点 $(x, y)$ 到边界的路径中出现的最大高度为「路径高度」,路径高度 $h$ 必然满足 $h >= heightMap[x][y]$。
问题的本质是求「从点 $(x, y)$ 到边界的所有路径高度的最小值为多少」,这个路径高度的最小值与 $(x, y)$ 本身的高度 $heightMap[x][y]$ 之间的差值,即是该点能接到的雨水数量。
PS. 对此觉得不好理解的同学,可以尝试从现实角度出发进行考虑:假如该位置是出水口(能够源源不断的出水并往各个方向蔓延),那么该位置最终承载多少水,取决于所有路径高度中的最小值(水流最终会被该路径高度的最小值所拦截),即出水口最终形成的水量为「路径高度最小值」与「出水口起始高度」之间的差值。
我们考虑如何计算某个位置 $(x, y)$ 的所有路径高度中的最小值。
如果是求从 $(x, y)$ 出发的所有路径中,路径总和的最小值,那么可以直接使用 Dijkstra 等单源最短路算法来进行求解。
本题求的是所有路径中,路径高度的最小值,需要对 Dijkstra 进行变形。
首先「从 $(x, y)$ 出发到达边界的路径」也可看作「从边界到达点 $(x, y)$ 的路径」,经过转换操作后,直接计算边界到点 $(x, y)$ 的路径是一个多源点问题。
我们可以考虑引入「超级源点」进行简化:超级源点与所有的边界格子连有一条权值为 $0$ 的边,从而进一步将问题转化为「求从超级源点出发到达 $(x, y)$ 的路径高度的最小值」。
与求最短路的 Dijkstra 类似,我们可以将「使用出队元素更新邻点的松弛操作」等价「使用出队元素更新相邻格子的雨水量」。
如果我们能够保证被出队元素所更新的高度为最终高度(或者说出队元素的高度为最终高度),那么该做法的正确性就能被 Dijkstra 的正确性所保证。
我们知道,对于边界格子而言,由于其不能接到任何雨水(即最终高度为起始高度),因此它们可以先进行入队。
然后考虑如何出队并更新邻点可以确保正确性。
对于某个位置 $(x, y)$ 而言,根据「木桶原理」,其最终高度取决于四个方向的邻点的最终高度的最小值。
这引导我们使用优先队列(堆)来做:建立一个小根堆,存储 $(x, y, h)$ 三元组信息( $h$ 为 位置 $(x, y)$ 的最终高度),每次使用出队元素来更新邻点,由于是小根堆,可以确保出队元素是被更新的元素的最小高度的邻点,并且被更新元素会被更新为最终高度,然后将被更新元素进行入队,重复此过程,直到所有位置均被更新。
实现上,我们不需要真将超级源点建立出来,只需要起始将所有边界点放入优先队列即可。同时由于每个点只有被第一个出队元素所更新的高度为最终高度,我们还需要使用 $vis$ 数组来避免重复更新。
代码: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
32class Solution {
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length;
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]);
boolean[][] vis = new boolean[m][n];
for (int i = 0; i < n; i++) {
q.add(new int[]{0, i, heightMap[0][i]});
q.add(new int[]{m - 1, i, heightMap[m - 1][i]});
vis[0][i] = vis[m - 1][i] = true;
}
for (int i = 1; i < m - 1; i++) {
q.add(new int[]{i, 0, heightMap[i][0]});
q.add(new int[]{i, n - 1, heightMap[i][n - 1]});
vis[i][0] = vis[i][n - 1] = true;
}
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int ans = 0;
while (!q.isEmpty()) {
int[] poll = q.poll();
int x = poll[0], y = poll[1], h = poll[2];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (vis[nx][ny]) continue;
if (h > heightMap[nx][ny]) ans += h - heightMap[nx][ny];
q.add(new int[]{nx, ny, Math.max(heightMap[nx][ny], h)});
vis[nx][ny] = true;
}
}
return ans;
}
}
- 时间复杂度:所有的点均进出一次优先队列(堆),复杂度为 $O((m n)\log{(m n)})$
- 空间复杂度:$O(m * n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.407
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!