concise C++ priority_queue solution


  • 15
    H
    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;
        }
    };
    

  • 0
    A

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


  • 0
    H

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


  • 0
    J
    This post is deleted!

  • 0
    D

    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;
        } 
    };
    

Log in to reply
 

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