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
| class Solution {
private static class Cell {
int row;
int col;
int height;
Cell(int _row, int _col, int _height) {
row = _row;
col = _col;
height = _height;
}
}
public int trapRainWater(int[][] heightMap) {
PriorityQueue<Cell> pq = new PriorityQueue<>((a, b) -> a.height - b.height);
boolean[][] visited = new boolean[heightMap.length][heightMap[0].length];
for (int i = 0; i < heightMap[0].length; i++) {
pq.offer(new Cell(0, i, heightMap[0][i]));
visited[0][i] = true;
pq.offer(new Cell(heightMap.length - 1, i, heightMap[heightMap.length - 1][i]));
visited[heightMap.length - 1][i] = true;
}
for (int i = 1; i < heightMap.length - 1; i++) {
pq.offer(new Cell(i, 0, heightMap[i][0]));
visited[i][0] = true;
pq.offer(new Cell(i, heightMap[0].length - 1, heightMap[i][heightMap[0].length - 1]));
visited[i][heightMap[0].length - 1] = true;
}
int ans = 0;
int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
while (!pq.isEmpty()) {
Cell currCell = pq.poll();
for (int[] direction : directions) {
int newRow = currCell.row + direction[0];
int newCol = currCell.col + direction[1];
if (!isOutOfBound(heightMap, newRow, newCol) && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
ans += Math.max(0, currCell.height - heightMap[newRow][newCol]);
pq.offer(new Cell(newRow, newCol, Math.max(currCell.height, heightMap[newRow][newCol])));
}
}
}
return ans;
}
private boolean isOutOfBound(int[][] grid, int row, int col) {
return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
}
}
|
这道题和pacific & atlantic那道题有些类似, 但是是那道题的升级版. 我们也是从border入手, 在border中我们挑最短的那个cell, 看它四周是否有比它小的没被visit过的cell, 首先border的cell肯定被visit过. 如果出现四周有个cell它的值比该border中最小的cell还要低, 那它一定可以存入水, 而且水面最大高度就是border中最小的cell的高度. 因为border上其他的cell都比它高, 因此能把水装起来. 但是水面可能比border中最小的height还高吗? 不可能, 因为会直接从border上最小height处流走. 然后我们把这个找到的cell放入queue中, 此时我们需要把它的height更新为它装完水后的高度, 因为下完雨后它的高度就是这么高, 因此可以成为其他cell的依靠. 我们可以认为此时我们把水首先给它放好到这个位置, 水被我们控制着不乱走.
如果遇到四周的cell的高度都很高, 那么我们也要把它放入queue中, 因为如果不放, 想象一下border中一圈还有个内层border, 它的高度比最外层border都要高. 此时如果我们只先把最外层border的cell都放入pq, 不把内部高的border的cell装入pq(只是因为它们更高), 此时内部即使内部border内可以存水, 我们也没考虑到. 因此是要放的.
时间复杂度: O(m * n) 每个cell最多进一次和出一次pq.
空间复杂度: O(m * n)
