给定一个m x n的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
说明:
m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。
示例:
给出如下 3x6 的高度图:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]
返回 4。
详见:https://leetcode.com/problems/trapping-rain-water-ii/description/
C++:
class Solution { public: int trapRainWater(vector<vector<int>>& heightMap) { if (heightMap.empty()) { return 0; } int m = heightMap.size(), n = heightMap[0].size(), 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]) { 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; } };
参考:https://www.cnblogs.com/grandyang/p/5928987.html