[Leetcode][407. 接雨水 II] 2种方法：优先队列存储每层围栏最低高度，BFS更新每个方块存水高度
By Long Luo
Leetcode 407. 接雨水 II 题目如下：
- 接雨水 II
给你一个 \(m \times n\) 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
示例 1:
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 输出: 4 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
示例 2:
输入: 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
这道题是 42. 接雨水 的3D版本，区别于2D版本只需要维护左右两个最高的木板，这里需要维护一个围栏，用堆（优先队列）来维护周围这个围栏中的最小元素。
方法一：优先队列 + 最小堆
思路与算法：
因为需要维护一个圈，用来存储水，所以需要从矩阵的最外围往里面遍历，不断缩小圈，直到遍历每个方块，在这个过程中计算每个方块能装多少水，更新 \(\textit{ans}\) 。
那么什么方块能存水呢？
- 该方块不是在圈外；
- 该方块高度比其上下左右四个相邻的方块接水后的高度都要低。
假设方块的索引为 \((i,j)\)，方块高度为 \(\textit{heightMap}[i][j]\)，方块接水后的高度为 \(\textit{water}[i][j]\)，则方块 \((i,j)\) 的接水后的高度为：
\[ \textit{water}[i][j] = \max( \textit{heightMap}[i][j], \min( \textit{water}[i-1][j], \textit{water}[i+1][j], \textit{water}[i][j-1], \textit{water}[i][j+1])) \]
每个方块 \((i,j)\) 实际接水量为：\(\textit{water}[i][j] - \textit{heightMap}[i][j]\)。
那问题变成了如何知道每个方块的 \(\textit{water}[i][j]\) 呢？
因为最外层的方块无法接水，所以最外层的方块接水后的高度 \(\textit{water}[i][j]=\textit{heightMap}[i][j]\)；
根据木桶原理，而每层水的高度则取决于每层方块中高度最低的方块；
从矩阵的四周边界开始，则可以知道最外层方块接水后的高度最小值。之后遍历每层中的每个方块周围\(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
39
40
41
42
43
44
45public int trapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.length <= 1 || heightMap[0].length <= 1) {
return 0;
}
int ans = 0;
int row = heightMap.length;
int col = heightMap[0].length;
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
boolean[][] visited = new boolean[row][col];
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
pq.offer(new int[]{i, j, heightMap[i][j]});
visited[i][j] = true;
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
for (int[] dir : dirs) {
int nextX = curr[0] + dir[0];
int nextY = curr[1] + dir[1];
if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || visited[nextX][nextY]) {
continue;
}
if (heightMap[nextX][nextY] < curr[2]) {
ans += curr[2] - heightMap[nextX][nextY];
}
visited[nextX][nextY] = true;
pq.offer(new int[]{nextX, nextY, Math.max(heightMap[nextX][nextY], curr[2])});
}
}
return ans;
}
复杂度分析
- 时间复杂度：\(O(MN \log (M+N))\)，其中 \(M\) 是矩阵的行数，\(N\) 是矩阵的列数。我们需要将矩阵中的每个元素都进行遍历，同时将每个元素都需要插入到优先队列中，总共需要向队列中插入 \(MN\) 个元素，每次堆进行调整的时间复杂度为 \(O(\log (M+N))\)，因此总的时间复杂度为 \(O(MN \log(M+N))\)。
- 空间复杂度：\(O(MN)\)，需要创建额外的空间对元素进行标记，优先队列中最多存储 \(O(MN)\) 个元素，因此空间复杂度度为 \(O(MN)\) 。
方法二：BFS
思路与算法：
假设初始时矩阵的每个格子都接满了水，且高度均为 \(\textit{maxHeight}\)，其中 \(\textit{maxHeight}\) 为矩阵中高度最高的格子。
接水后的高度为 \(\textit{water}[i][j]\)，方块 \((i,j)\) 的接水后的高度为：
\[ \textit{water}[i][j] = \max(\textit{heightMap}[i][j],\min(\textit{water}[i-1][j],\textit{water}[i+1][j],\textit{water}[i][j-1],\textit{water}[i][j+1])) \]
假设每个方块 \((i,j)\) 的接水后的高度均为 \(\textit{water}[i][j]=\textit{maxHeight}\)，那么：
- 最外层的方块的肯定不能接水；
- 如果当前方块 \((i,j)\) 的接水高度 \(\textit{water}[i][j]\) 小于与它相邻的 \(4\) 个方块接水高度时，调整接水高度，将其相邻的 \(4\) 个方块的接水高度调整为与 \((i,j)\) 的高度一致；
- 不断重复进行调整，直到所有的方块的接水高度不再有调整时即为满足要求。
最后根据方块 \((i,j)\) 接水容量 \(\textit{water}[i][j] - \textit{heightMap}[i][j]\)，遍历即为答案。
值得注意的是如果在BFS里运用 \(\textit{visited}\) 标记，反而在特殊情况下失败，因为在这里BFS如果遇到一个更低的高度，需要将原来已经遍历过的高度也更新，所以不能使用 \(\textit{visited}\) 标记。
代码如下所示：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
56
57
58
59
60
61
62public static int trapRainWater_bfs(int[][] heightMap) {
if (heightMap == null || heightMap.length <= 1 || heightMap[0].length <= 1) {
return 0;
}
int ans = 0;
int row = heightMap.length;
int col = heightMap[0].length;
int maxHeight = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
maxHeight = Math.max(maxHeight, heightMap[i][j]);
}
}
int[][] water = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
water[i][j] = maxHeight;
}
}
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
if (water[i][j] > heightMap[i][j]) {
water[i][j] = heightMap[i][j];
queue.offer(new int[]{i, j});
}
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
for (int[] dir : dirs) {
int nextX = curr[0] + dir[0];
int nextY = curr[1] + dir[1];
if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
continue;
}
// 只有比当前水位高才会流出水，water[nextX][nextY] > heightMap[nextX][nextY]是为了保证不会重复遍历。
if (water[curr[0]][curr[1]] < water[nextX][nextY] && water[nextX][nextY] > heightMap[nextX][nextY]) {
water[nextX][nextY] = Math.max(water[curr[0]][curr[1]], heightMap[nextX][nextY]);
queue.offer(new int[]{nextX, nextY});
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ans += water[i][j] - heightMap[i][j];
}
}
return ans;
}
复杂度分析
- 时间复杂度：\(O(M^2N^2)\) ，其中 \(M\) 是矩阵的行数， \(N\) 是矩阵的列数。每次发现有水面高度需要调整时，可能需要调整整个矩阵，因此时间复杂度为 \(O(M^2N^2)\) 。
- 空间复杂度：\(O(MN)\) ，需要创建额外的空间对每个元素进行标记，因此空间复杂度度为 \(O(MN)\) 。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗