Clear and readable cpp solution with priority_queue


  • 0
    Z
    class Solution {
    public:
    struct Node{
    int x;
    int y;
    int h;
    Node(int xc,int yc,int hc){
        x=xc,y=yc,h=hc;
    }
    bool operator<(const Node& r)const{
        return h>r.h;
    }
    };
    int trapRainWater(vector<vector<int>>& heightMap) {
        if(heightMap.size()<=2) return 0;
        priority_queue<Node> pq;
        int m=heightMap.size();
        int n=heightMap[0].size();
        int sum=0;
        vector<vector<bool>> hash(m,vector<bool>(n,false));
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        for(int i=0;i<n;i++){
            pq.push(Node(0,i,heightMap[0][i]));
            pq.push(Node(m-1,i,heightMap[m-1][i]));
            hash[0][i]=true;hash[m-1][i]=true;
        }
        for(int j=1;j<m-1;j++){
            pq.push(Node(j,0,heightMap[j][0]));
            pq.push(Node(j,n-1,heightMap[j][n-1]));
            hash[j][0]=true;hash[j][n-1]=true;
        }
        while(!pq.empty()){
            auto t = pq.top();
            pq.pop();
            for(int k=0;k<4;k++){
                int nx=t.x+dx[k],ny=t.y+dy[k];
                if(isValid(nx,ny,m,n) && !hash[nx][ny]){
                    hash[nx][ny]=true;
                    sum+=t.h>heightMap[nx][ny]?t.h-heightMap[nx][ny]:0;
                    pq.push(Node(nx,ny,max(t.h,heightMap[nx][ny])));
                }
            }
        }
        return sum;
    }
    bool isValid(int x,int y,int m,int n){
        return x>=0 && y>=0 && x<m && y<n;
    }
    };

Log in to reply
 

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