concise C++ priority_queue solution

• ``````class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if(heightMap.size()==0) return 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
int row = heightMap.size(), col = heightMap[0].size();
vector<vector<int>> visited(row, vector<int>(col, 0));
int ans = 0, Max = INT_MIN;
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
if(!(i==0 || i==row-1 || j==0 || j==col-1)) continue;
que.push(make_pair(heightMap[i][j], i*col+j));
visited[i][j] = 1;
}
}
vector<vector<int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while(!que.empty())
{
auto val = que.top(); que.pop();
int height = val.first, x = val.second/col, y = val.second%col;
Max = max(Max, height);
for(auto d: dir)
{
int x2 = x + d[0], y2 = y + d[1];
if(x2>=row || x2<0 || y2<0 || y2>=col || visited[x2][y2]) continue;
visited[x2][y2] = 1;
if(heightMap[x2][y2] < Max) ans += Max - heightMap[x2][y2];
que.push(make_pair(heightMap[x2][y2], x2*col+y2));
}
}
return ans;
}
};
``````

• Max is initialized to be INT_MIN and you do Max = min(Max, heightMap[i][j]);
Max is always INT_MIN?

• +antdavid actually that code do nothing, so I can remove it, I don't know why I wrote it. Thanks for your question.

• This post is deleted!

• Thanks for your sharing. I only changed the coding style.

``````class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int m = heightMap.size(), n = (m == 0) ? 0 : heightMap[0].size();
if(m < 3 || n < 3) return 0;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
vector<vector<int>> visited(m, vector<int>(n, 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;
pq.push(make_pair(heightMap[i][j], make_pair(i, j)));
visited[i][j] = 1;
}
}
vector<int> dir = {0, 1, 0, -1, 0};
int H = INT_MIN;
int res = 0;
while(!pq.empty())
{
auto p = pq.top(); pq.pop();
int height = p.first, i = p.second.first, j = p.second.second;
H = max(H, height);
for (int d = 0; d < 4; d++)
{
int x = i + dir[d], y = j + dir[d+1];
if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) continue;
visited[x][y] = 1;
int diff = H - heightMap[x][y];
if(diff > 0) res += diff;
pq.push(make_pair(heightMap[x][y], make_pair(x, y)));
}
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.