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 * 104
题解
由于能力有限
该方块不为最外层的方块； 该方块自身的高度比其上下左右四个相邻的方块接水后的高度都要低； 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/trapping-rain-water-ii/solution/jie-yu-shui-ii-by-leetcode-solution-vlj3/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { 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; } }
