你准备参加一场远足活动。给你一个二维 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] <= 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 原题链接和一些其他的优选题解。