专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友说订婚的前两个月老公（结婚之前应该叫相亲对象）被裁了，结果继续筹备婚礼，婚也结了，最后还是没有找到工作，已经失业四个月了，现在也不敢要孩子。
我觉得如果是程序员，失业4个月还找不到工作，可以考虑先找一份工作过渡一下，实在不行就转行吧。34岁确实挺尴尬的一个年龄，虽然现在各互联网大厂一直在招人，并且给的工资也不低，但他们主要招的是应届毕业生。
至于网友说的换个对象，当做玩笑看看就行了，不要当真。人无千日好，花无百日红，每个人都会经历过事业的低谷，只要别一直在低谷躺着就行。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第407题：接雨水 II
问题描述
来源：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 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=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.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 10^4
问题分析
对于3D接雨水问题，首先边上的位置是不能盛水的，只有里面的才有可能盛水。我们把边上围成的一圈看成一个桶，如下图所示：
根据木桶原理， 桶中水的高度取决于最小的那块木板 ，所以我们可以计算和最短木板挨着的位置（上下左右四个方向）所能容纳的水量，如果该位置比最短木板还高，明显是不能盛水的，该位置只有低于木板的高度，才会盛水。
每个位置计算之后，为了方便每次查找最小值，我们可以把计算之后的位置添加到最小堆中，下一次就从堆中继续取出最小值，在计算它的上下左右四个方向。。。
如下图所示，我们看到桶的一周最矮的是 4 ，计算和它挨着的高度为 3 的位置，他可以盛一个单位的水，盛水之后他的高度就变成 4 了。然后和里面的 4 挨着的有 8 和 9 ，他们都比 4 大，所以他们是不能盛水的。
接着我们再取出最小值 8 ，和它挨着的 6 是可以盛水的，一直重复上面的步骤，直到所有点都计算完为止。
我们还可以这样来想一下，因为使用的是BFS的遍历方式，每次都是从堆中取最小值遍历它的上下左右四个方向，而堆中的元素都是遍历过的，所以所有计算过的位置都是连通的，从最外面一圈开始，逐渐往内计算，类似于农村包围城市，最终全部包围。
JAVA：
public int trapRainWater(int[][] heightMap) { PriorityQueue
pq = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> a[2])); int m = heightMap.length;// 矩阵的高 int n = heightMap[0].length;// 矩阵的宽 boolean[][] visited = new boolean[m][n]; // 先把四周所有元素添加到堆中。 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) { pq.offer(new int[]{i, j, heightMap[i][j]}); visited[i][j] = true; } int water = 0;// 接的雨水量 // 上下左右 int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; while (!pq.isEmpty()) { int[] nums = pq.poll(); for (int[] dir : dirs) {// 遍历当前出队元素的上下左右四个方向。 int x = nums[0] + dir[1]; int y = nums[1] + dir[0]; // 不能越界 if (y < 0 || y >= n || x < 0 || x >= m || visited[x][y]) continue; visited[x][y] = true;// 标记为已计算过 water += Math.max(0, nums[2] - heightMap[x][y]);// 计算水量 pq.add(new int[]{x, y, Math.max(nums[2], heightMap[x][y])}); } } return water; }
C++：
public: int trapRainWater(vector
> &heightMap) { struct TupleCompare { bool operator()(const tuple
&a, const tuple
&b) const { return get<2>(a) > get<2>(b); } }; priority_queue int, int, int>, vector int, int, int>>, TupleCompare> pq; // 最小堆 int m = heightMap.size(); // 矩阵的高 int n = heightMap[ 0].size(); // 矩阵的宽 vector
> visited(m, vector
(n, false)); // 先把四周所有元素添加到堆中。 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) { pq.emplace(i, j, heightMap[i][j]); visited[i][j] = true; } int water = 0; // 接的雨水量 // 上下左右 int dirs[][ 2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; while (!pq.empty()) { tuple nums = pq.top(); pq.pop(); for ( const auto &dir: dirs) { // 遍历当前出队元素的上下左右四个方向。 int x = get< 1>(nums) + dir[ 0]; int y = get< 0>(nums) + dir[ 1]; // 不能越界 if (x < 0 || x >= n || y < 0 || y >= m || visited[y][x]) continue; visited[y][x] = true; // 标记为已计算过 water += max( 0, get< 2>(nums) - heightMap[y][x]); // 计算水量 pq.emplace(y, x, max(get< 2>(nums), heightMap[y][x])); } } return water; }
Python：
def trapRainWater(self, heightMap: List[List[int]]) -> int: pq = [] m = len(heightMap) # 矩阵的高 n = len(heightMap[0]) # 矩阵的宽 visited = [[False for _ in range(n)] for _ in range(m)] # 先把四周所有元素添加到堆中。 for i in range(m): for j in range(n): if i == 0 or i == m - 1 or j == 0 or j == n - 1: heapq.heappush(pq, (heightMap[i][j], i, j)) visited[i][j] = True water = 0 # 接的雨水量 # 上下左右 dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]] while pq: n0, n1, n2 = heapq.heappop(pq) for dx, dy in dirs: # 遍历当前出队元素的上下左右四个方向。 x = n1 + dx y = n2 + dy # 不能越界 if x < 0 or x >= m or y < 0 or y >= n or visited[x][y]: continue visited[x][y] = True # 标记为已计算过 water += max(0, n0 - heightMap[x][y]) # 计算水量 heapq.heappush(pq, (max(n0, heightMap[x][y]), x, y)) return water笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴