The article tries to explain leetcode 407. There is no satisfactory explanation online and honestly speaking I couldn't be convinced by my answer, either.
Problem:
Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
After observation we could say that:
- water level depends on the shortest block on the boundary
- The depth of water at one cell can not be greater or less than that of its neighbour
Most solutions online uses BFS and heap to simulate the process that the water level rises gradually out of the matrix and submerges the blocks. When polling out a block, we can guarantee that it's the shortest block on the boundary and all its shorter neighbours cannot hold water level higher than it. Actually I think of such solution and explanation too abstract and it seems that water is filling into the poll one cell by one cell. There should be a more intuitive explanation and sound mathematical proof. I will keep an eye on this question.
My code is as follows:
class Solution { private int[][] hm; private class Comp implements Comparator<int[]>{ public int compare(int[] a,int[] b){ if(hm[a[0]][a[1]]<hm[b[0]][b[1]])return -1; if(hm[a[0]][a[1]]==hm[b[0]][b[1]])return 0; return 1; } } public int trapRainWater(int[][] heightMap) { int m=heightMap.length; if(m<3)return 0; int n=heightMap[0].length; if(n<3)return 0; this.hm=heightMap; Queue<int[]> q=new PriorityQueue<int[]>(new Comp()); boolean[][] visit=new boolean[m][n]; int res=0; for(int i=0;i<n;i++){ q.offer(new int[]{0,i}); visit[0][i]=true; } for(int i=1;i<m-1;i++){ q.offer(new int[]{i,0}); visit[i][0]=true; q.offer(new int[]{i,n-1}); visit[i][n-1]=true; } for(int i=0;i<n;i++){ q.offer(new int[]{m-1,i}); visit[m-1][i]=true; } while(q.peek()!=null){ int[] u=q.poll(); int i=u[0]; int j=u[1]; if(i-1>=0 && !visit[i-1][j]){ visit[i-1][j]=true; if(heightMap[i][j]>heightMap[i-1][j]){ res+=heightMap[i][j]-heightMap[i-1][j]; heightMap[i-1][j]=heightMap[i][j]; } q.offer(new int[]{i-1,j}); } if(i+1<m && !visit[i+1][j]){ visit[i+1][j]=true; if(heightMap[i][j]>heightMap[i+1][j]){ res+=heightMap[i][j]-heightMap[i+1][j]; heightMap[i+1][j]=heightMap[i][j]; } q.offer(new int[]{i+1,j}); } if(j-1>=0 && !visit[i][j-1]){ visit[i][j-1]=true; if(heightMap[i][j]>heightMap[i][j-1]){ res+=heightMap[i][j]-heightMap[i][j-1]; heightMap[i][j-1]=heightMap[i][j]; } q.offer(new int[]{i,j-1}); } if(j+1<n && !visit[i][j+1]){ visit[i][j+1]=true; if(heightMap[i][j]>heightMap[i][j+1]){ res+=heightMap[i][j]-heightMap[i][j+1]; heightMap[i][j+1]=heightMap[i][j]; } q.offer(new int[]{i,j+1}); } } return res; } }
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
