407. 接雨水 II : 经典 Dijkstra 运用题

题目描述

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

Tag : 「图论最短路」、「优先队列（堆）」

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

示例 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^40<=heightMap[i][j]<=2∗104

Dijkstra 变形 + 优先队列（堆）

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

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

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

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

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

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

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

首先「从 (x, y)(x,y) 出发到达边界的路径」也可看作「从边界到达点 (x, y)(x,y) 的路

径」，经过转换操作后，直接计算边界到点 (x, y)(x,y) 的路径是一个多源点问题。

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

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

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

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

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

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

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

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

代码：

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)log(m∗n))
• 空间复杂度：O(m * n)O(m∗n)

最后

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

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

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

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