3D-TrappingRainWater 算法详解

2023-11-21
江苏
本文字数：2015 字
阅读完需：约 7 分钟

前言

3D-TrappingRainWater 算法还是有点难度的，活活脑子，解一解这道题还是挺有意思的。当然，本文给出的并非是最优解，如果你有更好的思路，也可自行动手常识。

原题

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

图1 示例

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]

Output: 4

Explanation: After the rain, water is trapped between the blocks.

We have two small ponds 1 and 3 units trapped.

The total volume of water trapped is 4.

Constraints:

m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104

解法

本文以最小堆来解，其时间复杂度为 $O (m n * l o g (m n))$ 。整体思路和关键步骤如下：

首先将二维矩阵的边界节点（也就是二维矩阵最外围的一圈节点）入队；
记录已访问过的节点路径，避免引起重复计算；
循环从队列中取出高度最小的节点，并计算与四周任意节点的高差来得到某块区域的盛水量；
将未访问过的节点入队并标记，始终优先处理最低高度的节点；
当最小堆为空时，即可得到二维矩阵的最终盛水量；

之所以采用最小堆，主要还是基于短板效应的考量，只要堆顶节点与四周任意节点的高差>0即可计算出某一块区域的盛水量，由外向内依次循环即可得出最终二维矩阵的整体盛水量。那么，我们首先需要想办法将二维矩阵的边界节点加入最小堆，并标记其 visted。

图1 边界节点入队

边界节点入队后，其节点高度最低的在堆顶，如图 1 所示，由于边界节点高度都是 2，那么假设坐标:3-1的节点2在堆顶，后续会优先展开计算。堆顶节点是短板，只要它大于它四周的任意节点（坐标3-1的节点只需要跟其上边节点比较即可，因为下边越界，左/右节点已经访问过），我们就可以计算出坐标2-1节点的盛水量。接下来，我们先来看看代码层面如何将二维矩阵的边界节点入队，如下所示：

var m = heights.length;var n = heights[0].length;var visited = new boolean[m][n];var queue = new PriorityQueue<int[]>((a, b) -> a[2] - b[2]);for (var i = 0; i < m; i++) {    for (var j = 0; j < n; j++) {        // 最外层标记为访问过        if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {            visited[i][j] = true;
            // 短板效应,始终先处理最低高度的点            queue.offer(new int[]{i, j, heights[i][j]});        }    }}

复制代码

上述程序示例中，最小堆中存储的是一个 int 类型的数组，主要用于存放节点的坐标和高度，而排序规则是节点高度最小的在前，同时使用 bool[][]来标记已处理过的边界节点的，避免后续的重复计算。

图2 盛水量计算过程

如图 2 所示，接下来我们只需要依次从队列中弹出堆顶元素，并计算它和四周的高差，直至最小堆为 null 为止即可得到二维矩阵的整体盛水量。代码如下所示：

var t1 = new int[]{0, 0, 1, -1};var t2 = new int[]{1, -1, 0, 0};while (!queue.isEmpty()) {    // 高度最低的点出队    var p = queue.poll();
    // 遍历目标的上下左右    for (var k = 0; k < 4; k++) {        var newX = p[0] + t1[k];        var newY = p[1] + t2[k];        // 判断访问路径边界和是否访问过        if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {            // 外围高度最低的点如果>当前点则计算盛水面积            rlt += Math.max(0, p[2] - heights[newX][newY]);            visited[newX][newY] = true;
            // 盛水后需要填充点的高度和外围高度最低的点相同(水流方向),然后入队按照由低到高依次处理            queue.offer(new int[]{newX, newY, Math.max(heights[newX][newY], p[2])});        }    }}

复制代码

上述程序示例中，有几个关键点大家需要注意，首先是越界和已经访问过的节点不会进行计算，其次满足条件的计算节点，其盛水量的计算一定要满足一个条件，那就是堆顶元素的高度要大于比较节点的高度，否则无法盛水，同时，我们还需要将堆顶节点与其比较节点高度的最大值（新节点）入队并标记，始终优先处理矩阵中最低高度的节点，试想一下，水往低处流，只有这样我们才能正确计算出下一个可盛水区域的盛水量。

图 2 中，坐标2-1是可以盛水的，盛水量为 1，其盛水后的高度为 2。当和其上方节点(坐标1-1)比较时，我们又同样可以得其盛水量为 1，因此这个二维矩阵的整体盛水量为 2。

九叔(高翔龙)

关注

Sleep 2020-03-25 加入

前支付宝高级技术专家，ArchSummit全球架构师峰会讲师、GIAC全球互联网架构大会讲师，著有畅销书《超大流量分布式系统架构解决方案》、《人人都是架构师》、《Java虚拟机精讲》

发布

暂无评论

创作场景

3D-TrappingRainWater 算法详解

前言

原题

解法

九叔(高翔龙)

评论