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。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/trapping-rain-water-ii

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

import java.util.Comparator;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {

    private int[] dx = {0, 1, 0, -1};

    private int[] dy = {1, 0, -1, 0};

    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
            return 0;
        }

        int ans = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(heightMap[o1[0]][o1[1]], heightMap[o2[0]][o2[1]]);
            }
        });

        int n = heightMap.length;
        int m = heightMap[0].length;
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < m - 1; ++i) {
            queue.offer(new int[]{0, i});
            visited[0][i] = true;

        }

        for (int i = 0; i < n - 1; ++i) {
            queue.offer(new int[]{i, m - 1});
            visited[i][m - 1] = true;
        }

        for (int i = m - 1; i > 0; --i) {
            queue.offer(new int[]{n - 1, i});
            visited[n - 1][i] = true;
        }

        for (int i = n - 1; i > 0; --i) {
            queue.offer(new int[]{i, 0});
            visited[i][0] = true;
        }

        int max = 0;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            max = Math.max(max, heightMap[node[0]][node[1]]);
            for (int i = 0; i < 4; ++i) {
                int x = dx[i] + node[0];
                int y = dy[i] + node[1];
                if (x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]) {
                    ans += Math.max(0, max - heightMap[x][y]);
                    visited[x][y] = true;
                    queue.offer(new int[]{x, y});
                }
            }

        }

        return ans;
    }
}
           

心之所向，素履以往 生如逆旅，一葦以航