题目描述
这是 LeetCode 上的 1631. 最小体力消耗路径 ，难度为 中等。
Tag : 「最小生成树」、「并查集」、「Kruskal」
你准备参加一场远足活动。
给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。
一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的「体力值」是路径上相邻格子之间「高度差绝对值」的「最大值」决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
示例 1：
输入：heights = [[1,2,2],[3,8,2],[5,3,5]] 输出：2 解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。 这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。 复制代码
示例 2：
输入：heights = [[1,2,3],[3,8,4],[5,3,5]] 输出：1 解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。 复制代码
示例 3：
输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出：0 解释：上图所示路径不需要消耗任何体力。 复制代码
提示：
- rows == heights.length
- columns == heights[i].length
- 1 <= rows, columns <= 100
- 1 <= heights[i][j] <= 10610^6106
基本分析
对于这道题，可能会有同学想这是不是应该用 DP 呀？
特别是接触过「路径问题」但又还没系统学完的同学。
事实上，当题目允许往任意方向移动时，考察的往往就不是 DP 了，而是图论。
从本质上说，DP 问题是一类特殊的图论问题。
那为什么有一些 DP 题目简单修改条件后，就只能彻底转化为图论问题来解决了呢？
这是因为修改条件后，导致我们 DP 状态展开不再是一个拓扑序列，也就是我们的图不再是一个拓扑图。
换句话说，DP 题虽然都属于图论范畴。
但对于不是拓扑图的图论问题，我们无法使用 DP 求解。
而此类看似 DP，实则图论的问题，通常是最小生成树或者最短路问题。
Kruskal
当一道题我们决定往「图论」方向思考时，我们的重点应该放在「如何建图」上。
因为解决某个特定的图论问题（最短路/最小生成树/二分图匹配），我们都是使用特定的算法。
由于使用到的算法都有固定模板，因此编码难度很低，而「如何建图」的思维难度则很高。
对于本题，我们可以按照如下分析进行建图：
因为在任意格子可以往「任意方向」移动，所以相邻的格子之间存在一条无向边。
题目要我们求的就是从起点到终点的最短路径中，边权最大的值。
我们可以先遍历所有的格子，将所有的边加入集合。
存储的格式为数组 [a,b,w][a, b, w][a,b,w] ，代表编号为 aaa 的点和编号为 bbb 的点之间的权重为 www。
按照题意，www 为两者的高度差的绝对值。
对集合进行排序，按照 www 进行从小到大排序（Kruskal 部分）。
当我们有了所有排好序的候选边集合之后，我们可以对边进行从前往后处理，每次加入一条边之后，使用并查集来查询「起点」和「终点」是否连通（并查集部分）。
当第一次判断「起点」和「终点」联通时，说明我们「最短路径」的所有边都已经应用到并查集上了，而且由于我们的边是按照「从小到大」进行排序，因此最后一条添加的边就是「最短路径」上权重最大的边。
代码：
class Solution { int N = 10009; int[] p = new int[N]; int row, col; void union(int a, int b) { p[find(a)] = p[find(b)]; } boolean query(int a, int b) { return p[find(a)] == p[find(b)]; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } public int minimumEffortPath(int[][] heights) { row = heights.length; col = heights[0].length; // 初始化并查集 for (int i = 0; i < row * col; i++) p[i] = i; // 预处理出所有的边 // edge 存的是 [a, b, w]：代表从 a 到 b 的体力值为 w // 虽然我们可以往四个方向移动，但是只要对于每个点都添加「向右」和「向下」两条边的话，其实就已经覆盖了所有边了 List<int[]> edges = new ArrayList<>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int idx = getIndex(i, j); if (i + 1 < row) { int a = idx, b = getIndex(i + 1, j); int w = Math.abs(heights[i][j] - heights[i + 1][j]); edges.add(new int[]{a, b, w}); } if (j + 1 < col) { int a = idx, b = getIndex(i, j + 1); int w = Math.abs(heights[i][j] - heights[i][j + 1]); edges.add(new int[]{a, b, w}); } } } // 根据权值 w 降序 Collections.sort(edges, (a,b)->a[2]-b[2]); // 从「小边」开始添加，当某一条边别应用之后，恰好使用得「起点」和「结点」联通 // 那么代表找到了「最短路径」中的「权重最大的边」 int start = getIndex(0, 0), end = getIndex(row - 1, col - 1); for (int[] edge : edges) { int a = edge[0], b = edge[1], w = edge[2]; union(a, b); if (query(start, end)) { return w; } } return 0; } int getIndex(int x, int y) { return x * col + y; } } 复制代码
令行数为 rrr，列数为 ccc，那么节点的数量为 r∗cr * cr∗c，无向边的数量严格为 r∗(c−1)+c∗(r−1)r * (c - 1) + c * (r - 1)r∗(c−1)+c∗(r−1)，数量级上为 r∗cr * cr∗c。
- 时间复杂度：获取所有的边复杂度为 O(r∗c)O(r * c)O(r∗c)，排序复杂度为 O((r∗c)log(r∗c))O((r * c)\log{(r * c)})O((r∗c)log(r∗c))，遍历得到最终解复杂度为 O(r∗c)O(r * c)O(r∗c)。整体复杂度为 O((r∗c)log(r∗c))O((r * c)\log{(r * c)})O((r∗c)log(r∗c))。
- 空间复杂度：使用了并查集数组。复杂度为 O(r∗c)O(r * c)O(r∗c)。
证明
我们之所以能够这么做，是因为「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是 www 最大的边」。
我们可以用「反证法」来证明这个结论为什么是正确的。
我们先假设「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是 www 最大的边」不成立：
我们令循环终止前的最后一条边为 a
- 假设 a 不在最优路径内：如果 aaa 并不在最优路径内，即最优路径是由 aaa 边之前的边构成，那么 aaa 边不会对左上角和右下角节点的连通性产生影响。也就是在遍历到该边之前，左上角和右下角应该是联通的，逻辑上循环会在遍历到该边前终止。与我们循环的决策逻辑冲突。
- aaa 在最优路径内，但不是 www 最大的边：我们在遍历之前就已经排好序。与排序逻辑冲突。
因此，我们的结论是正确的。a 边必然属于「最短路径」并且是权重最大的边。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1631 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
