#Problem

#⭐️⭐️⭐️⭐️⭐️

#Solution

Heap + Flood Fill

最外圈开始, 全部丢进一个priority queue. 从最低的elevation开始往四周渗透, 只要四周某个结点比当前的elevation低, 并且没有被访问过, 那么就把高度差值delta加入result. 否则如果仅仅只是没有访问过, 就丢进priority queue.

对于某一个当前的结点X, 如果它的四周有一个结点Y没有被访问过且elevation更低, 那说明什么? 说明Y四周其他三个结点都要比X高. 而Y所能盛水的量只能是上下左右里面最低的一个, 也就是X. 这也是为什么需要Heap的原因.

下次做的时候还不懂的话参考一下这个视频:
https://www.youtube.com/watch?v=cJayBq38VYw

#Time & Space

Time: O(M*N*Log(MN))
Space: O(M + N)

#Code

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
import java.util.PriorityQueue;
class Solution {
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length;
if (m == 0) return 0;
int n = heightMap[0].length;
if (n == 0) return 0;
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < m; i++) {
minHeap.add(new int[]{heightMap[i][0], i, 0});
minHeap.add(new int[]{heightMap[i][n - 1], i, n - 1});
heightMap[i][0] = -1;
heightMap[i][n - 1] = -1;
}
for (int j = 1; j < n - 1; j++) {
minHeap.add(new int[] {heightMap[0][j], 0, j});
minHeap.add(new int[] {heightMap[m - 1][j], m - 1, j});
heightMap[0][j] = -1;
heightMap[m - 1][j] = -1;
}
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int res = 0;
int currMax = 0;
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
currMax = Math.max(currMax, curr[0]);
for (int[] dir : dirs) {
int x = curr[1] + dir[0];
int y = curr[2] + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && heightMap[x][y] != -1) {
if (currMax > heightMap[x][y]) {
res += currMax - heightMap[x][y];
}
minHeap.offer(new int[] {heightMap[x][y], x, y});
heightMap[x][y] = -1;
}
}
}
return res;
}
}

Comments