首页 > 代码库 > 【Lintcode】364.Trapping Rain Water II
【Lintcode】364.Trapping Rain Water II
题目:
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 0; } int m = heightMap.size(), n = heightMap[0].size(); int res = 0, 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{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 || i == m - 1 || j == 0 || j == n - 1) { 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 = 0; i < dir.size(); ++i) { int x = r + dir[i][0], y = c + dir[i][1]; if (x < 0 || x >= m || y < 0 || 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; } };
【Lintcode】364.Trapping Rain Water II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。