407. 接雨水 II

---

前言

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

如图,里面的水全部都能接住

最外层都放入小根堆内

弹出4,以4为瓶颈,如果里面旁边的数小于4,那证明能接住
如果大于4,那么水就会从缺口流出

弹出3,现在还是4为瓶颈,看看附近能接多少水

只要max不更新,都是max的可以接水的区域
max更新的情况:
弹出的元素比max大

代码

class Solution {
    
    public static class Node{
    
        public int value;
        public int row;
        public int col;
        public Node(int v,int r,int c){
    
            value=v;
            row = r;
			col = c;
        }
    }
    public int trapRainWater(int[][] heightMap) {
    
        if (heightMap == null || heightMap.length == 0 || heightMap[0] == null || heightMap[0].length == 0) {
    
			return 0;
		}
        int n=heightMap.length;
        int m=heightMap[0].length;
        boolean[][] isEnter = new boolean[n][m];
        PriorityQueue<Node> heap=new PriorityQueue<Node>((a,b)->a.value-b.value);
        for(int i=1;i<n-1;i++){
    
            heap.add(new Node(heightMap[i][0],i,0));
            isEnter[i][0]=true;
            heap.add(new Node(heightMap[i][m-1],i,m-1));
            isEnter[i][m-1]=true;
        }
        for(int i=0;i<m;i++){
    
            heap.add(new Node(heightMap[0][i],0,i));
            isEnter[0][i]=true;
            heap.add(new Node(heightMap[n-1][i],n-1,i));
            isEnter[n-1][i]=true;
        }
        int water=0;
        int max=0;
        while(!heap.isEmpty()){
    
            Node node=heap.poll();
            max=Math.max(max,node.value);
            int r=node.row;
            int c=node.col;
            if(r>0&&!isEnter[r-1][c]){
    
                isEnter[r-1][c]=true;
                water+=Math.max(0,max-heightMap[r-1][c]);
                heap.add(new Node(heightMap[r-1][c],r-1,c));
            }
            if(r<n-1&&!isEnter[r+1][c]){
    
                isEnter[r+1][c]=true;
                water+=Math.max(0,max-heightMap[r+1][c]);
                heap.add(new Node(heightMap[r+1][c],r+1,c));
            }
            if(c>0&&!isEnter[r][c-1]){
    
                isEnter[r][c-1]=true;
                water+=Math.max(0,max-heightMap[r][c-1]);
                heap.add(new Node(heightMap[r][c-1],r,c-1));
            }
            if(c<m-1&&!isEnter[r][c+1]){
    
                isEnter[r][c+1]=true;
                water+=Math.max(0,max-heightMap[r][c+1]);
                heap.add(new Node(heightMap[r][c+1],r,c+1));
            }
        }
        return water;
    }
}