本文共 897 字，大约阅读时间需要 2 分钟。

尝试过DFS搜索最小边界写这道题，很麻烦，总有反例。

正手应该是模拟水面上升，比较容易懂。

随着水面上升，

class Solution {public: struct Node{    int h;    int x;    int y;    Node(int a,int b,int c):h(a),x(b),y(c){};    bool operator < (const Node a) const{        if(a.h < this->h) return true;        return false;    }};int trapRainWater(vector
   
    
     >& heightMap) {    int R = heightMap.size();    if( R <= 2) return 0;    int C = heightMap[0].size();    if( C <= 2) return 0;    priority_queue
     
      
       > q;      vector
       
        
         > v(R,vector
         
          (C,0)); const int dirx[] = {-1,0,1,0}; const int diry[] = {0,1,0,-1}; for(int i=0;i
          
           = R-1 || c < 1 || c >= C-1 || v[r][c]) continue; v[r][c] = 1; if(heightMap[r][c] < mWall){ ans += mWall - heightMap[r][c]; heightMap[r][c] = mWall; } q.push(*(new Node(heightMap[r][c],r,c))); } } return ans;}};
          
         
        
       
      
     
    
   

转载地址：http://uiwji.baihongyu.com/