题目:
Given n x m non-negative integers representing an elevation map 2d where the area of each cell is 1 x 1, compute how much water it is able to trap after raining.
Example
Given 5*4
matrix
[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]
return 14
.
题解:
之前的题是Two pointer, 本质是在给定的边界不断向中心遍历,这道题也是,不过边界由两端变成了四个边,同样是内缩遍历。而且这道题还需要堆的思想来从最小端开始遍历(防止漏水)。详见 here。
Solution 1 () (from here 转自Granyang)
class Solution {
public:
int trapRainWater(vector<vector<int> > &heightMap) {
if (heightMap.empty()) {
return ;
}
int m = heightMap.size(), n = heightMap[].size();
int res = , mx = INT_MIN;
priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int, int>>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<vector<int>> dir{{, -}, {-, }, {, }, {, }};
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
if (i == || i == m - || j == || j == n - ) {
q.push({heightMap[i][j], i * n + j});
visited[i][j] = true;
}
}
} while (!q.empty()) {
auto t = q.top();
q.pop();
int h = t.first, r = t.second / n, c = t.second % n;
mx = max(mx, h);
for (int i = ; i < dir.size(); ++i) {
int x = r + dir[i][], y = c + dir[i][];
if (x < || x >= m || y < || y >= n || visited[x][y] == true) continue;
visited[x][y] = true;
if (heightMap[x][y] < mx) res += mx - heightMap[x][y];
q.push({heightMap[x][y], x * n + y});
}
}
return res;
}
};