LC 407. 接雨水 II

题目描述

这是 LeetCode 上的 407. 接雨水 II ，难度为 困难。

给你一个 $m x n$ 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例 1:

1
2
3
4
5
输入: 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:

1
2
3
输入: 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$

Dijkstra 变形 + 优先队列（堆）

首先，最外层的一圈（边界）是不会接到任何雨水的（会从边界流出）。

我们定义从点 $(x, y)$ 到边界的路径中出现的最大高度为「路径高度」，路径高度 $h$ 必然满足 $h >= heightMap[x][y]$。

问题的本质是求「从点 $(x, y)$ 到边界的所有路径高度的最小值为多少」，这个路径高度的最小值与 $(x, y)$ 本身的高度 $heightMap[x][y]$ 之间的差值，即是该点能接到的雨水数量。

PS. 对此觉得不好理解的同学，可以尝试从现实角度出发进行考虑：假如该位置是出水口（能够源源不断的出水并往各个方向蔓延），那么该位置最终承载多少水，取决于所有路径高度中的最小值（水流最终会被该路径高度的最小值所拦截），即出水口最终形成的水量为「路径高度最小值」与「出水口起始高度」之间的差值。

我们考虑如何计算某个位置 $(x, y)$ 的所有路径高度中的最小值。

如果是求从 $(x, y)$ 出发的所有路径中，路径总和的最小值，那么可以直接使用 Dijkstra 等单源最短路算法来进行求解。

本题求的是所有路径中，路径高度的最小值，需要对 Dijkstra 进行变形。

首先「从 $(x, y)$ 出发到达边界的路径」也可看作「从边界到达点 $(x, y)$ 的路径」，经过转换操作后，直接计算边界到点 $(x, y)$ 的路径是一个多源点问题。

我们可以考虑引入「超级源点」进行简化：超级源点与所有的边界格子连有一条权值为 $0$ 的边，从而进一步将问题转化为「求从超级源点出发到达 $(x, y)$ 的路径高度的最小值」。

与求最短路的 Dijkstra 类似，我们可以将「使用出队元素更新邻点的松弛操作」等价「使用出队元素更新相邻格子的雨水量」。

如果我们能够保证被出队元素所更新的高度为最终高度（或者说出队元素的高度为最终高度），那么该做法的正确性就能被 Dijkstra 的正确性所保证。

我们知道，对于边界格子而言，由于其不能接到任何雨水（即最终高度为起始高度），因此它们可以先进行入队。

然后考虑如何出队并更新邻点可以确保正确性。

对于某个位置 $(x, y)$ 而言，根据「木桶原理」，其最终高度取决于四个方向的邻点的最终高度的最小值。

这引导我们使用优先队列（堆）来做：建立一个小根堆，存储 $(x, y, h)$ 三元组信息（ $h$ 为 位置 $(x, y)$ 的最终高度），每次使用出队元素来更新邻点，由于是小根堆，可以确保出队元素是被更新的元素的最小高度的邻点，并且被更新元素会被更新为最终高度，然后将被更新元素进行入队，重复此过程，直到所有位置均被更新。

实现上，我们不需要真将超级源点建立出来，只需要起始将所有边界点放入优先队列即可。同时由于每个点只有被第一个出队元素所更新的高度为最终高度，我们还需要使用 $vis$ 数组来避免重复更新。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]);
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < n; i++) {
            q.add(new int[]{0, i, heightMap[0][i]});
            q.add(new int[]{m - 1, i, heightMap[m - 1][i]});
            vis[0][i] = vis[m - 1][i] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            q.add(new int[]{i, 0, heightMap[i][0]});
            q.add(new int[]{i, n - 1, heightMap[i][n - 1]});
            vis[i][0] = vis[i][n - 1] = true;
        }
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        int ans = 0;
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int x = poll[0], y = poll[1], h = poll[2];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (vis[nx][ny]) continue;
                if (h > heightMap[nx][ny]) ans += h - heightMap[nx][ny];
                q.add(new int[]{nx, ny, Math.max(heightMap[nx][ny], h)});
                vis[nx][ny] = true;
            }
        }
        return ans;
    }
}

  • 时间复杂度：所有的点均进出一次优先队列（堆），复杂度为 $O((m n)\log{(m n)})$
  • 空间复杂度：$O(m * n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.407 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。