BiliBili
YouTube
原题
中文
给定一个 m x n 的矩阵,其中的值均为正整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
说明
m 和 n 都是小于110的整数。每一个单位的高度都大于 0 且小于 20000。
英文
Given an m x n
matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.
Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.
Example:
Given the following 3x6 height map: [ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1] ] Return 4.

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
before the rain.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.
思路

代码
struct Node{
int r;
int c;
int h;
Node(int row, int col, int height) : r(row), c(col), h(height) {};
bool operator>(Node a) const {return h > a.h;};
};
class Solution {
public:
int trapRainWater(vector<vector<int>>& hm) {
int r = 0, c = 0;
if ((r = hm.size()) == 0 || (c = hm[0].size()) == 0) return 0;
vector<vector<int>> vis(r, vector<int>(c, 0));
priority_queue<Node, vector<Node>, greater<Node> > pq;
for (int i = 0; i < c; ++i) {
pq.push(Node(0, i, hm[0][i]));
pq.push(Node(r - 1, i, hm[r - 1][i]));
vis[0][i] = 1;
vis[r - 1][i] = 1;
}
for (int i = 1; i < r - 1; ++i) {
pq.push(Node(i, 0, hm[i][0]));
pq.push(Node(i, c - 1, hm[i][c - 1]));
vis[i][0] = 1;
vis[i][c - 1] = 1;
}
int water = 0, vis_max = INT_MIN;
vector<int> d{0, -1, 0, 1, 0};
while (!pq.empty()) {
auto node = pq.top();
pq.pop();
water += (vis_max > node.h) ? vis_max - node.h : 0;
vis_max = max(vis_max, node.h);
for (int di = 0; di < 4; ++di) {
int nr = node.r + d[di];
int nc = node.c + d[di + 1];
if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
if (vis[nr][nc] == 1) continue;
vis[nr][nc] = 1;
pq.push(Node(nr, nc, hm[nr][nc]));
}
}
return water;
}
};
复杂度分析
时间复杂度:O(n \log n) n = m * n
空间复杂度:O(n)
参考
原题链接:https://leetcode.com/problems/trapping-rain-water-ii/
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/leetcode-407-trapping-rain-water-ii/
3whitening
[…] 阅读原文 […]