接雨水Ⅱ

题目描述

原题链接：407. 接雨水 II - 力扣（LeetCode）

给你一个 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

解题思路

参考接接雨水 - 子川个人博客 (qgcatg.top)中的堆解法

代码

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int n = heightMap.length;
        int m = heightMap[0].length;
        // 优先队列(位置， 高度)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[2]-b[2]);
        boolean[][] si = new boolean[n+10][m+10];
        // 初态为heightMap的四周的元素
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i==0 || j==0 || i == n-1 || j==m-1){
                    pq.offer(new int[]{i,j,heightMap[i][j]});
                    si[i][j] = true;
                }
            }
        }
        int[] xx = {0, 0, 1, -1};
        int[] yy = {1, -1, 0, 0};
        int ans = 0;
        while(!pq.isEmpty()){
            // 取出第一个元素
            int[] tmp = pq.poll();
            // 看看四周
            for(int i = 0; i < 4; i++){
                int x = tmp[0] + xx[i], y = tmp[1] + yy[i];
                if(x >= 0 && x < n && y >= 0 && y < m && !si[x][y]){
                    int tmp_s = heightMap[x][y];
                    if(tmp_s < tmp[2]){
                        ans += tmp[2] - tmp_s;
                    }
                    pq.offer(new int[]{x, y, Math.max(tmp_s, tmp[2])});
                    si[x][y] = true;
                }
            }
        }
        return ans;
    }
}