Article / 文章
LeetCode第407题：接雨水 II
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
难度：困难
题目链接：LeetCode第407题
题目描述
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
示例 1：
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为4。示例 2：
输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10提示：
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104
解题思路
这道题目是经典题目“接雨水”的二维版本，核心思路是：
- 使用优先队列（最小堆）从外向内处理
- 维护一个“木桶”，其高度由最短的木板决定
- 从矩阵边界开始，按照高度从低到高的顺序处理每个位置
算法流程
-
初始化：
- 创建优先队列，存储位置和高度
- 将矩阵边界的所有位置加入队列
- 使用visited数组标记已访问的位置
-
BFS处理：
- 每次从队列中取出高度最小的位置
- 检查其四个相邻位置：
- 如果相邻位置未访问：
- 如果相邻位置高度小于当前高度，可以接水
- 将相邻位置加入队列（使用max(当前高度, 相邻位置高度)）
- 如果相邻位置未访问：
-
累计结果：
- 对于每个可以接水的位置，计算可以接的水量
- 水量 = 当前高度 - 位置原始高度
代码实现
C# 实现
public class Solution {
public int TrapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.Length <= 2 || heightMap[0].Length <= 2) {
return 0;
}
int m = heightMap.Length;
int n = heightMap[0].Length;
bool[,] visited = new bool[m, n];
// 使用优先队列（C#中使用SortedSet模拟）
var pq = new SortedSet<(int height, int row, int col)>();
// 添加边界
for (int i = 0; i < m; i++) {
pq.Add((heightMap[i][0], i, 0));
pq.Add((heightMap[i][n-1], i, n-1));
visited[i,0] = visited[i,n-1] = true;
}
for (int j = 1; j < n-1; j++) {
pq.Add((heightMap[0][j], 0, j));
pq.Add((heightMap[m-1][j], m-1, j));
visited[0,j] = visited[m-1,j] = true;
}
int result = 0;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (pq.Count > 0) {
var curr = pq.Min;
pq.Remove(curr);
// 检查四个方向
for (int k = 0; k < 4; k++) {
int nx = curr.row + dx[k];
int ny = curr.col + dy[k];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx,ny]) {
visited[nx,ny] = true;
// 如果新位置比当前高度低，可以接水
if (heightMap[nx][ny] < curr.height) {
result += curr.height - heightMap[nx][ny];
pq.Add((curr.height, nx, ny));
} else {
pq.Add((heightMap[nx][ny], nx, ny));
}
}
}
}
return result;
}
}Python 实现
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
if not heightMap or len(heightMap) <= 2 or len(heightMap[0]) <= 2:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False] * n for _ in range(m)]
# 使用优先队列
pq = []
# 添加边界
for i in range(m):
heapq.heappush(pq, (heightMap[i][0], i, 0))
heapq.heappush(pq, (heightMap[i][n-1], i, n-1))
visited[i][0] = visited[i][n-1] = True
for j in range(1, n-1):
heapq.heappush(pq, (heightMap[0][j], 0, j))
heapq.heappush(pq, (heightMap[m-1][j], m-1, j))
visited[0][j] = visited[m-1][j] = True
result = 0
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while pq:
height, row, col = heapq.heappop(pq)
# 检查四个方向
for dx, dy in directions:
nx, ny = row + dx, col + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
visited[nx][ny] = True
# 如果新位置比当前高度低，可以接水
if heightMap[nx][ny] < height:
result += height - heightMap[nx][ny]
heapq.heappush(pq, (height, nx, ny))
else:
heapq.heappush(pq, (heightMap[nx][ny], nx, ny))
return resultC++ 实现
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
if (heightMap.size() <= 2 || heightMap[0].size() <= 2) {
return 0;
}
int m = heightMap.size();
int n = heightMap[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
// 使用优先队列
priority_queue<pair<int, pair<int, int>>,
vector<pair<int, pair<int, int>>>,
greater<pair<int, pair<int, int>>>> pq;
// 添加边界
for (int i = 0; i < m; i++) {
pq.push({heightMap[i][0], {i, 0}});
pq.push({heightMap[i][n-1], {i, n-1}});
visited[i][0] = visited[i][n-1] = true;
}
for (int j = 1; j < n-1; j++) {
pq.push({heightMap[0][j], {0, j}});
pq.push({heightMap[m-1][j], {m-1, j}});
visited[0][j] = visited[m-1][j] = true;
}
int result = 0;
vector<pair<int, int>> directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
int height = curr.first;
int row = curr.second.first;
int col = curr.second.second;
// 检查四个方向
for (const auto& dir : directions) {
int nx = row + dir.first;
int ny = col + dir.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
visited[nx][ny] = true;
// 如果新位置比当前高度低，可以接水
if (heightMap[nx][ny] < height) {
result += height - heightMap[nx][ny];
pq.push({height, {nx, ny}});
} else {
pq.push({heightMap[nx][ny], {nx, ny}});
}
}
}
}
return result;
}
};执行结果
C# 实现
- 执行用时：124 ms
- 内存消耗：44.2 MB
Python 实现
- 执行用时：92 ms
- 内存消耗：16.8 MB
C++ 实现
- 执行用时：16 ms
- 内存消耗：12.4 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 124 ms | 44.2 MB | 使用SortedSet模拟优先队列，性能较差 |
| Python | 92 ms | 16.8 MB | 使用heapq，代码简洁 |
| C++ | 16 ms | 12.4 MB | 原生优先队列，性能最优 |
代码亮点
- 🎯 使用优先队列实现从外向内的处理策略
- 💡 巧妙运用木桶原理解决二维接水问题
- 🔍 完善的边界条件处理
- 🎨 各语言实现都保持了良好的可读性
常见错误分析
- 🚫 忽略边界条件检查
- 🚫 优先队列使用最大堆而不是最小堆
- 🚫 访问标记处理不当
- 🚫 方向数组定义错误
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 优先队列BFS | O(mnlog(m+n)) | O(mn) | 实现相对简单 | 空间消耗较大 |
| 动态规划 | O(mn) | O(mn) | 理论性能好 | 不易实现，不直观 |
相关题目
- LeetCode 42. 接雨水 - 困难
- LeetCode 417. 太平洋大西洋水流问题 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第407题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！