接雨水Ⅱ

LC 407.接雨水Ⅱ

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

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=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


class Solution {
    int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int trapRainWater(int[][] heightMap) {
        int res = 0;
        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[2] - b[2];
        });
        boolean[][] vis = new boolean[m][n];

        // 将外围包围
        for (int i = 0; i < m; i++) {
            pq.offer(new int[]{i, 0, heightMap[i][0]});
            vis[i][0] = true;
            pq.offer(new int[]{i, n-1, heightMap[i][n-1]});
            vis[i][n-1] = true;
        }
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{0, i, heightMap[0][i]});
            vis[0][i] = true;
            pq.offer(new int[]{m-1, i, heightMap[m-1][i]});
            vis[m-1][i] = true;
        }

        while (!pq.isEmpty()) {
            // 从中取最小高度的点
            int[] ar = pq.poll();
            for (int[] d : dir) {
                // 遍历四个方向
                int x = ar[0] + d[0], y = ar[1] + d[1];
                if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                    if (heightMap[x][y] < ar[2]) {
                        res += ar[2] - heightMap[x][y];
                    }
                    pq.offer(new int[]{x, y, Math.max(heightMap[x][y], ar[2])});   // 决定本坐标的高度
                    vis[x][y] = true;
                }
            }
        }
        return res;
    }
}

LC 407.接雨水Ⅱ

相关文章：