大家好，这里是张哈希刷题频道。今天给大家带来一道有意思的题目，"接雨水II"。
看到好多小伙伴，遇到了面试官想 `kill -9` 结束面试，抛出了这个3D接雨水核弹（前些年抛红黑树线段树之类的），接不下来基本上就宣布下线，此时一般可以直接带上简历走人了 ... （开个玩笑，可以继续厚脸皮硬刚，坚持住我们能赢）
这个题目听起来很恐怖，其实是个老派难题。我们从头到尾把这个题目的解决过程讲解一遍。
题目分析
首先来看题目,题目大意是给你一个二维的height map,让你求这个地形能够接的雨水总量。height map里面的每个格子的高度是不同的,雨水能存在低洼处但不能流到更高的地方,最后你要算出地形中雨水的总量。
这么一个题目最直观的解法就是边遍历边计算了,对于每个位置尝试遍历它的上下左右,找到它能够承载雨水的最大高度。然后四个方向找最小值,这个值就是该位置可以存放的雨水量。
上面的思路很简单,但是实现起来就比较麻烦了:你得维护一个可以随时找到四个方向最大高度的数据结构,对于每个位置都要计算四个方向的最大值。暴力做法,需要三层循环,所以时间复杂度 O(m * n * min(m, n))。
不过细想下来,这道题也不是非得上下左右计算不可,我们可以想个更巧妙的做法。
现在说一个时间复杂度比较高级的解法。
正餐
这个解法的思路也很易懂:从外围（上下左右四个边界）开始扫描,用一个小根堆维护当前 height map 剩余的低洼区域。
首先把四周的格子都加入这个小根堆, 然后从小根堆中取出高度最低的格子（并每次都维护一个max用于判断当前已经从最小堆中弹出的最高柱子，方便我们用 “高 - 低” 得出低洼的单位值）, 看看它能不能接雨水。遍历它上下左右的格子, 观察能否蓄水。
即：max = 1； max-heightMap[row][col] < 0;
Math.max(0, max-heightMap[row][col]) = 0，边界的低洼不接雨水
如果能蓄水,就计算出它能蓄多少水,把蓄水量加到结果上（如果外围柱子标记为max后发现比四周的要低，则无法蓄水）。无论能不能蓄水,都把周围不在小根堆中的低洼格子加入小根堆,这样才不会漏掉中心区域的低洼区域。以此类推,最终小根堆中就只有最中心的高地,全部低洼区域都被遍历并计算过了。
不看也不会做,还得上代码:
/**
* 小根堆
* 时间：O( mn * log(mn) )
* 空间：O( m*n)
* @param heightMap
* @return
*/
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length, max = Integer.MIN_VALUE, ans = 0; // max：全局max
PriorityQueue<Node> minHeap = new PriorityQueue<>(((o1, o2) -> o1.height - o2.height));
boolean[][] visited = new boolean[m][n];
// 1）将四周一圈加入小根堆：
for (int col = 0; col < n; col++) {
addToHeap(heightMap, minHeap, visited, 0, col, max);
addToHeap(heightMap, minHeap, visited, m - 1, col, max);
}
for (int row = 0; row < m; row++) {
addToHeap(heightMap, minHeap, visited, row, 0, max);
addToHeap(heightMap, minHeap, visited, row, n - 1, max);
}
// 2）从小根堆弹出节点，弹出时更新全局max，再将其上下左右分别拉入小根堆，入堆时结算其位置的水量：
while (!minHeap.isEmpty()) {
Node node = minHeap.poll();
max = Math.max(max, node.height); // 更新全局max
ans += addToHeap(heightMap, minHeap, visited, node.row - 1, node.col, max);
ans += addToHeap(heightMap, minHeap, visited, node.row + 1, node.col, max);
ans += addToHeap(heightMap, minHeap, visited, node.row, node.col - 1, max);
ans += addToHeap(heightMap, minHeap, visited, node.row, node.col + 1, max);
}
return ans;
}
// heightMap[row][col]入堆，并返回当前[row][col]位置的接水量
private int addToHeap(int[][] heightMap, PriorityQueue<Node> minHeap, boolean[][] visited,
int row, int col, int max) {
if (row >= 0 && row < heightMap.length && col >= 0 && col < heightMap[0].length && !visited[row][col]) {
minHeap.add(new Node(heightMap[row][col], row, col));
visited[row][col] = true;
return Math.max(0, max - heightMap[row][col]);
}
return 0;
}
private static class Node {
int height;
int row, col;
public Node(int height, int row, int col) {
this.height = height;
this.row = row;
this.col = col;
}
}- 首先，我们创建一个小根堆，用于存储每个单元格的高度和位置。同时，我们还需要一个布尔数组
visited来记录哪些单元格已经被访问过。 - 然后，我们将地图四周的所有单元格加入到小根堆中，并标记为已访问。
- 接下来，我们开始主要的循环。在每次循环中，我们从小根堆中取出一个节点（即一个单元格），并更新全局最大高度
max。然后，我们将该节点的上、下、左、右四个邻居单元格加入到小根堆中，并计算每个邻居单元格的接水量。这个接水量等于全局最大高度max减去邻居单元格的高度，如果结果为负，则接水量为0。 - 最后，当小根堆为空时，我们就计算出了所有单元格的接水量，将它们相加，就得到了最终的答案。
核心代码35行，可以说很妙了，掐表20分钟基本不可能bugfree，背诵吧少年~
这里主要代码量就集中在 addToHeap 这个函数了,需要控制边界,并且做接雨水量的计算。接雨水量的计算就是 max(0, 局部最高高度 - 当前格子高度),这是因为如果局部最高高度比当前格子高度还要低,那就意味着当前低洼区已经遍历完了,不可能存水。
以上就是这道题目的的两个解法思路,前一种是用了左右两个辅助数组的暴力做法,后一种是基于小根堆的解法。文章来源：https://www.toymoban.com/news/detail-832592.html
小根堆解法,外加入堆和弹出堆的操作,理论时间复杂度是 O(mn * log(mn))。文章来源地址https://www.toymoban.com/news/detail-832592.html
到了这里，关于leetcode 407.接雨水II(超级简单易懂)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
