0407. Trapping Rain Water II¶
题目信息¶
- 题号:
0407
- 难度:
Hard
- 主题:
二维地形、边界泄水、四邻接、总蓄水量
- 原题:
- 重点:
每格表示单位柱体高度、水可从外边界流走、只通过上下左右连通、返回所有格子的总蓄水量
题目重述¶
给定 m × n 的非负整数矩阵 heightMap,每个格子表示一个底面积为 1 的柱体高度。降雨后,水可以在由较高地形围住的低洼处积存,也可以沿上下左右相邻格子流动并从矩阵外边界流出。
返回整个地形最终能够储存的水量总和。矩阵行列数均位于 [1, 200],每个高度位于 [0, 2 * 10^4]。对角线接触不形成连通通道;位于外边界的格子自身不能依靠矩阵外侧形成挡水墙。
自建示例¶
单个封闭低点:
输入:heightMap = [[3,3,3],[3,1,3],[3,3,3]]
输出:2
解释:中心格高度为 1,四周最低边界高度为 3,因此中心可以储存 2 个单位的水。
四邻接边界缺口限制水位:
输入:heightMap = [[4,1,4],[4,0,4],[4,4,4]]
输出:1
解释:中心格与高度为 1 的上边界格四邻接,水位超过 1 就会从该缺口流出,因此中心只能储存 1 个单位。
从外边界维护当前最低挡水墙¶
水能否留在内部取决于它到外界路径上的最低边界。把所有边界格先放入按高度排序的最小堆,并标记已访问;每次取出当前最低的边界格,检查四邻格。若邻格更低,它能储存 边界高度 - 邻格高度 的水;随后把邻格以 max(邻格地形高度, 当前边界高度) 作为新的有效边界压入堆。
这样堆中的高度表示从已探索区域向外的最低泄水门槛,而不是单纯的原始地形高度。边界格只入堆一次,四邻接检查也不会把对角接触当作通道。
C++ 实现¶
class Solution {
using Cell = std::tuple<int, int, int>;
public:
int trapRainWater(std::vector<std::vector<int>>& heightMap) {
int rows = static_cast<int>(heightMap.size());
int cols = static_cast<int>(heightMap[0].size());
if (rows < 3 || cols < 3) return 0;
std::priority_queue<Cell, std::vector<Cell>,
std::greater<Cell>> boundary;
std::vector<std::vector<bool>> visited(
rows, std::vector<bool>(cols, false));
auto push = [&](int row, int col) {
if (visited[row][col]) return;
visited[row][col] = true;
boundary.emplace(heightMap[row][col], row, col);
};
for (int row = 0; row < rows; ++row) {
push(row, 0);
push(row, cols - 1);
}
for (int col = 1; col + 1 < cols; ++col) {
push(0, col);
push(rows - 1, col);
}
const int directions[4][2] = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
int water = 0;
while (!boundary.empty()) {
auto [level, row, col] = boundary.top();
boundary.pop();
for (const auto& direction : directions) {
int nextRow = row + direction[0];
int nextCol = col + direction[1];
if (nextRow < 0 || nextRow >= rows
|| nextCol < 0 || nextCol >= cols
|| visited[nextRow][nextCol]) {
continue;
}
visited[nextRow][nextCol] = true;
water += std::max(
0, level - heightMap[nextRow][nextCol]);
boundary.emplace(
std::max(level, heightMap[nextRow][nextCol]),
nextRow, nextCol);
}
}
return water;
}
};
代码分析¶
最小堆每次扩展全局最低有效边界,邻格一旦被访问就确定其能够达到的最低外部水位;若地形低于该水位,差值就是可储水量。每个格子入堆一次,时间复杂度为 O(mn log(mn)),额外空间为 O(mn)。