【刷穿 LeetCode】1631. 最小体力消耗路径（中等）
【刷穿 LeetCode】1631. 最小体力消耗路径（中等）
题目描述
你准备参加一场远足活动。给你一个二维 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.lengthcolumns == heights[i].length1 <= rows, columns <= 1001 <= heights[i][j] <= 106
并查集解法
由于在任意点可以往任意方向移动，所以相邻的点之间存在一条无向边。
我们可以先遍历所有的点，将所有的边加入集合，存储的格式为数组 [a, b, w] ，代表编号为 a 的点和编号为 b 的点之间的权重为 w（按照题意，w 为两者的高度差的绝对值）。
对集合进行排序，按照 w 进行从小到达排序。
当我们有了所有排好序的候选边集合之后，我们可以对边从前往后处理，每次加入一条边之后，使用并查集来查询左上角的点和右下角的点是否连通。
当我们的合并了某条边之后，判定左上角和右下角的点联通，那么该边的权重即是答案。
class Solution {
int N = 10009;
int[] p = new int[N];
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];
}
int row, col;
public int minimumEffortPath(int[][] heights) {
row = heights.length;
col = heights[0].length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int idx = getIndex(i, j);
p[idx] = idx;
if (i + 1 < row) edges.add(new int[]{idx, getIndex(i + 1, j), Math.abs(heights[i][j] - heights[i + 1][j])});
if (j + 1 < col) edges.add(new int[]{idx, getIndex(i, j + 1), Math.abs(heights[i][j] - heights[i][j + 1])});
}
}
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;
}
}
令行数为 r，列数为 c，那么节点的数量为 r * c，无向边的数量严格为 r * (c - 1) + c * (r - 1)，数量级上为 r * c。
- 时间复杂度：获取所有的边复杂度为
，排序复杂度为
，遍历得到最终解复杂度为
。整体复杂度为
。
- 空间复杂度：使用了并查集数组。复杂度为
证明
我们使用反证法来证明一下为什么这样的做法是对的。
我们假设「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是 w 最大的边」不成立：
我们令循环终止前的最后一条边为 a
假设 a 不在最优路径内：如果 a 并不在最优路径内，即最优路径是由 a 边之前的边构成，那么 a 边不会对左上角和右下角节点的连通性产生影响。也就是在遍历到该边之前，左上角和右下角应该是联通的，逻辑上循环会在遍历到该边前终止。与我们循环的决策逻辑冲突。a 在最优路径内，但不是 w 最大的边：我们在遍历之前就已经排好序。与排序逻辑冲突。
得证「跳出循环前所遍历的最后一条边必然是最优路径上的边，而且是 w 最大的边」。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
腾讯云开发者
