Algorithm Practice
Search…
407 Trapping Rain Water II
1. Question
Given an
m x nmatrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.Note:
Bothmandnare less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
1
Given the following 3x6 height map:
2
[
3
[1,4,3,1,3,2],
4
[3,2,1,3,2,4],
5
[2,3,3,2,3,1]
6
]
7
8
Return 4.
Copied!
The above image represents the elevation map
[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]before the rain.
After the rain, water are trapped between the blocks. The total volume of water trapped is 4.
2. Implementation
(1) BFS
1
public class Solution {
2
class Cell implements Comparable<Cell>{
3
int row;
4
int col;
5
int height;
6
7
public Cell(int row, int col, int height) {
8
this.row = row;
9
this.col = col;
10
this.height = height;
11
}
12
13
public int compareTo(Cell that) {
14
return this.height - that.height;
15
}
16
}
17
18
public int trapRainWater(int[][] heightMap) {
19
if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
20
return 0;
21
}
22
23
int m = heightMap.length, n = heightMap[0].length;
24
boolean[][] visited = new boolean[m][n];
25
PriorityQueue<Cell> queue = new PriorityQueue<>();
26
27
for (int i = 0; i < m; i++) {
28
for (int j = 0; j < n; j++) {
29
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
30
queue.add(new Cell(i, j, heightMap[i][j]));
31
visited[i][j] = true;
32
}
33
}
34
}
35
36
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
37
int curMaxHeight = 0;
38
int res = 0;
39
40
while (!queue.isEmpty()) {
41
Cell curCell = queue.remove();
42
curMaxHeight = Math.max(curMaxHeight, curCell.height);
43
44
for (int[] direction : directions) {
45
int nextRow = curCell.row + direction[0];
46
int nextCol = curCell.col + direction[1];
47
48
if (isValid(heightMap, nextRow, nextCol, visited)) {
49
visited[nextRow][nextCol] = true;
50
queue.add(new Cell(nextRow, nextCol, heightMap[nextRow][nextCol]));
51
52
if (heightMap[nextRow][nextCol] < curMaxHeight) {
53
res += curMaxHeight - heightMap[nextRow][nextCol];
54
}
55
}
56
}
57
}
58
return res;
59
}
60
61
public boolean isValid(int[][] heightMap, int row, int col, boolean[][] visited) {
62
return row >= 0 && row < heightMap.length && col >= 0 && col < heightMap[0].length && !visited[row][col];
63
}
64
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度O(mn), 空间复杂度O(mn)