题目
给你一个 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
解题
动态规划（此方法在三维中没法用）
很快就想到将动态规划的方法从二维的接雨水引申到三维的接雨水中，但是存在侧漏的情况，如果仅仅只是求4个方向最高是不行的。
比如一个三维图的左视图和主视图都是这个样子，那么中心那个柱子，可以放3格水吗？显然会发生侧漏
class Solution { public: inline int minH(int a,int b,int c,int d){ return min(min(a,b),min(c,d)); } int trapRainWater(vector<vector<int>>& heightMap) { int m=heightMap.size(),n=heightMap[0].size(); vector<vector<int>> heightW(m,vector<int>(n,0)); vector<vector<int>> heightS(m,vector<int>(n,0)); vector<vector<int>> heightA(m,vector<int>(n,0)); vector<vector<int>> heightD(m,vector<int>(n,0)); for(int j=0;j<n;j++) heightW[0][j]=heightMap[0][j]; for(int i=1;i<m;i++){ for(int j=0;j<n;j++){ heightW[i][j]=max(heightW[i-1][j],heightMap[i][j]); } } for(int j=0;j<n;j++) heightS[m-1][j]=heightMap[m-1][j]; for(int i=m-2;i>=0;i--){ for(int j=0;j<n;j++){ heightS[i][j]=max(heightS[i+1][j],heightMap[i][j]); } } for(int i=0;i<m;i++) heightA[i][0]=heightMap[i][0]; for(int j=1;j<n;j++){ for(int i=0;i<m;i++){ heightA[i][j]=max(heightA[i][j-1],heightMap[i][j]); } } for(int i=0;i<m;i++) heightD[i][n-1]=heightMap[i][n-1]; for(int j=n-2;j>=0;j--){ for(int i=0;i<m;i++){ heightD[i][j]=max(heightD[i][j+1],heightMap[i][j]); } } int res=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ res+=minH(heightA[i][j],heightD[i][j],heightW[i][j],heightS[i][j])-heightMap[i][j]; } } return res; } };
方法一：优先队列
核心思想就是先确定木桶的外围，找到外围的最短板子后对其周围能填水的地方填水，然后更新木桶外围
根据木桶原理，接到的雨水由容器周围最短的木板决定的，开始取决于最外圈
通过优先队列，每次可以取到最短的木板
将3填充成了水，变成4，可以把它当作成新的容器的外圈，这样一步步迭代
class Solution { public: int trapRainWater(vector<vector<int>>& heightMap) { int m=heightMap.size(),n=heightMap[0].size(); priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; vector<vector<bool>> visited(m,vector<bool>(n,false)); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0||i==m-1||j==0||j==n-1){ q.emplace(heightMap[i][j],i*n+j); visited[i][j]=true; } } } int dirs[5]={-1,0,1,0,-1}; int res=0; while(!q.empty()){ auto [h,index]=q.top(); q.pop(); for(int i=0;i<4;i++){ int nx=index/n+dirs[i]; int ny=index%n+dirs[i+1]; if(nx<0||nx>=m||ny<0||ny>=n||visited[nx][ny]) continue; if(heightMap[nx][ny]<h){ res+=h-heightMap[nx][ny]; } visited[nx][ny]=true; q.emplace(max(heightMap[nx][ny],h),nx*n+ny); } } return res; } };
