By Long Luo
Leetcode 407. 接雨水 II 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 407. 接雨水 II 给你一个m x 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版本只需要维护左右两个最高的木板,这里需要维护一个围栏,用堆(优先队列)来维护周围这个围栏中的最小元素。
方法一:优先队列 + 最小堆
思路与算法:
因为需要维护一个圈,用来存储水,所以需要从矩阵的最外围往里面遍历,不断缩小圈,直到遍历每个方块,在这个过程中计算每个方块能装多少水,更新 ans \textit{ans} ans 。
那么什么方块能存水呢?
该方块不是在圈外;
该方块高度比其上下左右四个相邻的方块接水后的高度都要低。
假设方块的索引为 ( i , j ) (i,j) ( i , j ) ,方块高度为 heightMap [ i ] [ j ] \textit{heightMap}[i][j] heightMap [ i ] [ j ] ,方块接水后的高度为 water [ i ] [ j ] \textit{water}[i][j] water [ i ] [ j ] ,则方块 ( i , j ) (i,j) ( i , j ) 的接水后的高度为:
water [ i ] [ j ] = max ( heightMap [ i ] [ j ] , min ( water [ i − 1 ] [ j ] , water [ i + 1 ] [ j ] , water [ i ] [ j − 1 ] , 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]))
water [ i ] [ j ] = max ( heightMap [ i ] [ j ] , min ( water [ i − 1 ] [ j ] , water [ i + 1 ] [ j ] , water [ i ] [ j − 1 ] , water [ i ] [ j + 1 ] ) )
每个方块 ( i , j ) (i,j) ( i , j ) 实际接水量为:water [ i ] [ j ] − heightMap [ i ] [ j ] \textit{water}[i][j] - \textit{heightMap}[i][j] water [ i ] [ j ] − heightMap [ i ] [ j ] 。
那问题变成了如何知道每个方块的 water [ i ] [ j ] \textit{water}[i][j] water [ i ] [ j ] 呢?
因为最外层的方块无法接水,所以最外层的方块接水后的高度 water [ i ] [ j ] = heightMap [ i ] [ j ] \textit{water}[i][j]=\textit{heightMap}[i][j] water [ i ] [ j ] = heightMap [ i ] [ j ] ;
根据木桶原理,而每层水的高度则取决于每层方块中高度最低的方块;
从矩阵的四周边界开始,则可以知道最外层方块接水后的高度最小值。之后遍历每层中的每个方块周围4 4 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 45 public 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 ( M N log ( M + N ) ) O(MN\log(M+N)) O ( M N log ( M + N ) ) ,其中 M M M 是矩阵的行数,N N N 是矩阵的列数。我们需要将矩阵中的每个元素都进行遍历,同时将每个元素都需要插入到优先队列中,总共需要向队列中插入 M N MN M N 个元素,每次堆进行调整的时间复杂度为 O ( log ( M + N ) ) O(\log(M+N)) O ( log ( M + N ) ) ,因此总的时间复杂度为 O ( M N log ( M + N ) ) O(MN\log(M+N)) O ( M N log ( M + N ) ) 。
空间复杂度:O ( M N ) O(MN) O ( M N ) ,需要创建额外的空间对元素进行标记,优先队列中最多存储 O ( M N ) O(MN) O ( M N ) 个元素,因此空间复杂度度为 O ( M N ) O(MN) O ( M N ) 。
方法二:BFS
思路与算法:
假设初始时矩阵的每个格子都接满了水,且高度均为 maxHeight \textit{maxHeight} maxHeight ,其中 maxHeight \textit{maxHeight} maxHeight 为矩阵中高度最高的格子。
接水后的高度为 water [ i ] [ j ] \textit{water}[i][j] water [ i ] [ j ] ,方块 ( i , j ) (i,j) ( i , j ) 的接水后的高度为:
water [ i ] [ j ] = max ( heightMap [ i ] [ j ] , min ( water [ i − 1 ] [ j ] , water [ i + 1 ] [ j ] , water [ i ] [ j − 1 ] , 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]))
water [ i ] [ j ] = max ( heightMap [ i ] [ j ] , min ( water [ i − 1 ] [ j ] , water [ i + 1 ] [ j ] , water [ i ] [ j − 1 ] , water [ i ] [ j + 1 ] ) )
假设每个方块 ( i , j ) (i,j) ( i , j ) 的接水后的高度均为 water [ i ] [ j ] = maxHeight \textit{water}[i][j]=\textit{maxHeight} water [ i ] [ j ] = maxHeight ,那么:
最外层的方块的肯定不能接水;
如果当前方块 ( i , j ) (i,j) ( i , j ) 的接水高度 water [ i ] [ j ] \textit{water}[i][j] water [ i ] [ j ] 小于与它相邻的 4 4 4 个方块接水高度时,调整接水高度,将其相邻的 4 4 4 个方块的接水高度调整为与 ( i , j ) (i,j) ( i , j ) 的高度一致;
不断重复进行调整,直到所有的方块的接水高度不再有调整时即为满足要求。
最后根据方块 ( i , j ) (i,j) ( i , j ) 接水容量 water [ i ] [ j ] − heightMap [ i ] [ j ] \textit{water}[i][j] - \textit{heightMap}[i][j] water [ i ] [ j ] − heightMap [ i ] [ j ] ,遍历即为答案。
值得注意的是如果在BFS 里运用 visited \textit{visited} visited 标记,反而在特殊情况下失败,因为在这里BFS 如果遇到一个更低的高度,需要将原来已经遍历过的高度也更新,所以不能使用 visited \textit{visited} 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 62 public 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 ; } 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; }
复杂度分析
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 . 😉😃💗