(1) Use minimum heap to store the height for most outer boarder and scan from the lowest height.
(2) For the top height in the heap (h1), we need to record the lowest height (it's the maxH in the code). (Why? Because it is the lowest height in the most out boundary, we expect it to grow only. If there is any height lower than current lowest height, it has trapped water.) If it has neighbor with lower height (h2), then the neighbor must be able to hold water (maxH - h2). Why? Because at this time the boundary has been updated and maxH is the lowest height so far, please see step (3).
(3) Mark the neighbor as visited and push it to the heap. Since the neighbor has been visited, the boundary is updated.
(4) repeat (2) - (3) until heap becomes empty.
1: class Solution {
2: public:
3: int trapRainWater(vector<vector<int>>& heightMap) {
4: if (heightMap.empty()) return 0;
5: int rows = heightMap.size(), cols = heightMap[0].size();
6: priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
7: vector<vector<bool>> visited(rows, vector<bool>(cols, false));
8: for (int i = 0; i < rows; i++) {
9: for (int j = 0; j < cols; j++) {
10: if (i == 0 || i == rows-1 || j == 0 || j == cols-1) {
11: q.push(make_pair(heightMap[i][j], i*cols+j));
12: visited[i][j] = true;
13: }
14: }
15: }
16: vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
17: int res = 0, maxH = INT_MIN;
18: while (!q.empty()) {
19: int height = q.top().first;
20: int i = q.top().second / cols, j = q.top().second % cols;
21: q.pop();
22: maxH = max(maxH, height);
23: for (int d = 0; d < dir.size(); d++) {
24: int ii = i + dir[d].first;
25: int jj = j + dir[d].second;
26: if (ii < 0 || jj < 0 || ii == rows || jj == cols || visited[ii][jj]) continue;
27: visited[ii][jj] = true;
28: if (heightMap[ii][jj] < maxH) res += maxH - heightMap[ii][jj];
29: q.push(make_pair(heightMap[ii][jj], ii*cols+jj));
30: }
31: }
32: return res;
33: }
34: };
