文章目录
前言
解题思路
代码
前言
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
Interlaken Protocol白皮书(中文)
0星
超过10%的资源
851KB
下载
输入: 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;
}
}
