# Trapping Rain Water1,2 优先队列解法

```class Solution {
public:
int trap(vector<int>& height) {
pair<int,int> que;
int len = height.size();
if(len<3) return 0;
int res = 0;
que.first = 0;
que.second = len-1;
int Max = -1;
while(que.first<que.second)
{
//Max = max(height[que.first],height[que.second]);
if(height[que.first]<=height[que.second])
{
if(height[que.first]>Max) Max = height[que.first];
if(Max>height[que.first+1]) res+=Max - height[que.first+1];
que.first++;
}
else
{
if(Max<height[que.second]) Max = height[que.second];
if(Max>height[que.second-1]) res+= Max-height[que.second-1];
que.second--;
}

}
return res;
}
};```
```class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {

int res = 0;

int m = heightMap.size();
if(m==0) return 0;
int n = heightMap[0].size();
priority_queue < pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater< pair<int,pair<int,int>> > > que;

vector<vector<int> > visited(m,vector<int>(n,0));

int dir[] = {0,1,0,-1,0};

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)) continue;
que.push(make_pair(heightMap[i][j],make_pair(i,j)));
visited[i][j] = 1;

}
}

int MAX = -10;
while(!que.empty())
{
pair<int,pair<int,int>> temp = que.top();que.pop();
if(temp.first>MAX) MAX = temp.first;

int x = temp.second.first;
int y = temp.second.second;

for(int i=0;i<4;i++)
{
int a = x+dir[i];
int b = y+dir[i+1];

if(a>=0&&a<m&&b>=0&&b<n&&visited[a][b]==0)
{
que.push(make_pair(heightMap[a][b],make_pair(a,b)));
if(MAX > heightMap[a][b])  res += MAX - heightMap[a][b];
visited[a][b] = 1;
}
}
}
return res;
}
};```

53 篇文章29 人订阅

0 条评论