Trapping Rain Water I & II (Leet

这两道题的一个要点在于，由于柱子是有宽度的，所以有外向里时，仅里面高度低时才有可能灌水。所以我们compare 内高和外高，当外面高时加入水，当内部高时继续往里扫。

Trapping Rain Water I:

int trapRainWater(vector<int> &heights) {
        // write your code here
        if(heights.empty()) return 0;
        int left = 0, right = heights.size()-1;
        int ret = 0, leftHeight = heights[left], rightHeight = heights[right];
        while(left < right){
            if(leftHeight < rightHeight){
                left++;
                if(heights[left] < leftHeight){
                    ret += leftHeight - heights[left];
                }else{
                    leftHeight = heights[left];
                }
            }else{
                right--;
                if(heights[right] < rightHeight){
                    ret += rightHeight - heights[right];
                }else{
                    rightHeight = heights[right];
                }
            }
        }
        return ret;
    }

Trapping Rain Water II:
二就是建立priority queue，从四周往里扫。而二的要点是当外面高时，把外面高度+里面坐标，放入priority queue

class Solution {
public:
    
    struct Node{
        int row, col;
        int height;
        Node(int r, int c, int h) : row(r), col(c), height(h){}
    };
    
    int trapRainWater(vector<vector<int>>& heightMap) {
        if(heightMap.empty() || heightMap[0].empty()){
            return 0;
        }
        
        int row = heightMap.size(), col = heightMap[0].size();
        auto comp = [](const Node &n1, const Node &n2){
            return n1.height > n2.height;  // min heap
        };
        
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        priority_queue<Node, vector<Node>, decltype(comp)> pque(comp);
        
        for(int i=0; i<row; i++){
            pque.push(Node(i, 0, heightMap[i][0]));
            pque.push(Node(i, col-1, heightMap[i][col-1]));
            visited[i][0] = true;
            visited[i][col-1] = true;
        }
        
        for(int i=0; i<col; i++){
            pque.push(Node(0, i, heightMap[0][i]));
            pque.push(Node(row-1, i, heightMap[row-1][i]));
            visited[0][i] = true;
            visited[row-1][i] = true;
        }
        
        int ret = 0;
        while(!pque.empty()){
            Node cur = pque.top(); pque.pop();
            for(auto it : directions){
                int x = cur.row + it.first, y = cur.col + it.second;
                if(x < 0 || x >= row || y < 0 || y >= col || visited[x][y]){
                    continue;
                }
                visited[x][y] = true;
                if(heightMap[x][y] < cur.height){
                    ret += cur.height - heightMap[x][y];
                }
                pque.push(Node(x, y, max(cur.height, heightMap[x][y])));
            }
        }
        return ret;        
    }
};