【Leetcode算法题】407. 接雨水 II

By Long Luo

今天Leetcode的每日一题是:407. 接雨水 II,题目如下:

  1. 接雨水 II

给你一个m x n的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。

示例 1:

3D 接雨水 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:

3D 接雨水 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

方法一:BFS

思路与算法:

我们假设初始时矩阵的每个格子都接满了水,且高度均为maxHeight\textit{maxHeight},其中maxHeight\textit{maxHeight}为矩阵中高度最高的格子。我们知道方块接水后的高度为water[i][j]\textit{water}[i][j],它的求解公式与方法一样。方块(i,j)(i,j)的接水后的高度为:

water[i][j]=max(heightMap[i][j],min(water[i1][j],water[i+1][j],water[i][j1],water[i][j+1]))\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)(i,j)际接水的容量计算公式为water[i][j]heightMap[i][j]\textit{water}[i][j] - \textit{heightMap}[i][j]
我们首先假设每个方块(i,j)(i,j)的接水后的高度均为water[i][j]=maxHeight\textit{water}[i][j] = \textit{maxHeight},首先我们知道最外层的方块的肯定不能接水,所有的多余的水都会从最外层的方块溢出,我们每次发现当前方块(i,j)(i,j)的接水高度water[i][j]\textit{water}[i][j]小于与它相邻的44个模块的接水高度时,则我们将进行调整接水高度,我们将其相邻的四个方块的接水高度调整与(i,j)(i,j)的高度保持一致,我们不断重复的进行调整,直到所有的方块的接水高度不再有调整时即为满足要求。

代码如下所示:

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
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length;
int n = heightMap[0].length;
int[] dirs = {-1, 0, 1, 0, -1};
int maxHeight = 0;

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
maxHeight = Math.max(maxHeight, heightMap[i][j]);
}
}
int[][] water = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j){
water[i][j] = maxHeight;
}
}
Queue<int[]> qu = new LinkedList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
if (water[i][j] > heightMap[i][j]) {
water[i][j] = heightMap[i][j];
qu.offer(new int[]{i, j});
}
}
}
}
while (!qu.isEmpty()) {
int[] curr = qu.poll();
int x = curr[0];
int y = curr[1];
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
}
if (water[x][y] < water[nx][ny] && water[nx][ny] > heightMap[nx][ny]) {
water[nx][ny] = Math.max(water[x][y], heightMap[nx][ny]);
qu.offer(new int[]{nx, ny});
}
}
}

int res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
res += water[i][j] - heightMap[i][j];
}
}
return res;
}

复杂度分析:

  • 时间复杂度:O(M2N2)O(M^2N^2),其中MM是矩阵的行数,NN是矩阵的列数。因此每次发现有水面高度需要调整时,可能需要调整整个矩阵,因此时间复杂度为O(M2N2)O(M^2N^2)

  • 空间复杂度:O(MN)O(MN),其中MM是矩阵的行数,NN是矩阵的列数。我们需要创建额外的空间对每个元素进行标记,因此空间复杂度度为O(MN)O(MN)

方法二: 最小堆

思路与算法:

首先我们思考一下什么样的方块一定可以接住水:

  • 该方块不为最外层的方块;
  • 该方块自身的高度比其上下左右四个相邻的方块接水后的高度都要低;

我们假设方块的索引为(i,j)(i,j),方块的高度为heightMap[i][j]\textit{heightMap}[i][j],方块接水后的高度为water[i][j]\textit{water}[i][j]。则我们知道方块(i,j)(i,j)的接水后的高度为:

water[i][j]=max(heightMap[i][j],min(water[i1][j],water[i+1][j],water[i][j1],water[i][j+1]))\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)(i,j)实际接水的容量计算公式为water[i][j]heightMap[i][j]\textit{water}[i][j] - \textit{heightMap}[i][j]

首先我们可以确定的是,矩阵的最外层的方块接水后的高度就是方块的自身高度,因为最外层的方块无法接水,因此最外层的方块water[i][j]=heightMap[i][j]\textit{water}[i][j] = \textit{heightMap}[i][j]

根据木桶原理,接到的雨水的高度由这个容器周围最短的木板来确定的。我们可以知道容器内水的高度取决于最外层高度最低的方块,如图11所示:

图1

我们假设已经知道最外层的方块接水后的高度的最小值,则此时我们根据木桶原理,肯定可以确定最小高度方块的相邻方块的接水高度。我们同时更新最外层的方块标记,我们在新的最外层的方块再次找到接水后的高度的最小值,同时确定与其相邻的方块的接水高度,如图22所示:

图2

然后再次更新最外层,依次迭代直到求出所有的方块的接水高度,即可知道矩阵中的接水容量。

代码如下所示:

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
public int trapRainWater(int[][] heightMap) {
if (heightMap.length <= 2 || heightMap[0].length <= 2) {
return 0;
}
int m = heightMap.length;
int n = heightMap[0].length;
boolean[][] visit = new boolean[m][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
pq.offer(new int[]{i * n + j, heightMap[i][j]});
visit[i][j] = true;
}
}
}
int res = 0;
int[] dirs = {-1, 0, 1, 0, -1};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
for (int k = 0; k < 4; ++k) {
int nx = curr[0] / n + dirs[k];
int ny = curr[0] % n + dirs[k + 1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
if (curr[1] > heightMap[nx][ny]) {
res += curr[1] - heightMap[nx][ny];
}
pq.offer(new int[]{nx * n + ny, Math.max(heightMap[nx][ny], curr[1])});
visit[nx][ny] = true;
}
}
}
return res;
}

复杂度分析:

  • 时间复杂度:O(MNlog(M+N))O(MN\log(M+N)),其中MM是矩阵的行数,NN是矩阵的列数。我们需要将矩阵中的每个元素都进行遍历,同时将每个元素都需要插入到优先队列中,总共需要向队列中插入MNMN个元素,每次堆进行调整的时间复杂度为O(log(M+N))O(\log(M+N)),因此总的时间复杂度为O(MNlog(M+N))O(MN\log(M+N))

  • 空间复杂度:O(MN)O(MN),其中MM是矩阵的行数,NN是矩阵的列数。我们需要创建额外的空间对元素进行标记,优先队列中最多存储O(MN)O(MN)个元素,因此空间复杂度度为O(MN)O(MN)