题目描述
这是 LeetCode 上的 1631. 最小体力消耗路径 ,难度为 中等。
你准备参加一场远足活动。
给你一个二维 rows x columns
的地图 heights
,其中 heights[row][col]
表示格子 (row, col)
的高度。
一开始你在最左上角的格子 (0, 0
) ,且你希望去最右下角的格子 (rows-1, columns-1)
(注意下标从 0 开始编号)。
你每次可以往「上,下,左,右」四个方向之一移动,你想要找到耗费体力最小的一条路径。
一条路径耗费的「体力值」是路径上相邻格子之间「高度差绝对值」的「最大值」决定的。
请你返回从左上角走到右下角的最小体力消耗值。
示例 1:

| 输入:heights =
输出:2
解释:路径 连续格子的差值绝对值最大为 2 。 这条路径比路径 更优,因为另一条路径差值最大值为 3 。
|
示例 2:
| 输入:heights =
输出:1
解释:路径 的相邻格子差值绝对值最大为 1 ,比路径 更优。
|
示例 3:
| 输入:heights =
输出:0
解释:上图所示路径不需要消耗任何体力。
|
提示:
- $rows = heights.length$
- $columns = heights[i].length$
- $1 <= rows, columns <= 100$
- $1 <= heights[i][j] <= 10^6$
基本分析
对于这道题,可能会有同学想这是不是应该用 DP 呀?
特别是接触过「路径问题」但又还没系统学完的同学。
事实上,当题目允许往任意方向移动时,考察的往往就不是 DP 了,而是图论。
从本质上说,DP 问题是一类特殊的图论问题。
那为什么有一些 DP 题目简单修改条件后,就只能彻底转化为图论问题来解决了呢?
这是因为修改条件后,导致我们 DP 状态展开不再是一个拓扑序列,也就是我们的图不再是一个拓扑图。
换句话说,DP 题虽然都属于图论范畴。
但对于不是拓扑图的图论问题,我们无法使用 DP 求解。
而此类看似 DP,实则图论的问题,通常是最小生成树或者最短路问题。
Kruskal
当一道题我们决定往「图论」方向思考时,我们的重点应该放在「如何建图」上。
因为解决某个特定的图论问题(最短路/最小生成树/二分图匹配),我们都是使用特定的算法。
由于使用到的算法都有固定模板,因此编码难度很低,而「如何建图」的思维难度则很高。
对于本题,我们可以按照如下分析进行建图:
因为在任意格子可以往「任意方向」移动,所以相邻的格子之间存在一条无向边。
题目要我们求的就是从起点到终点的最短路径中,边权最大的值。
我们可以先遍历所有的格子,将所有的边加入集合。
存储的格式为数组 $[a, b, w]$ ,代表编号为 $a$ 的点和编号为 $b$ 的点之间的权重为 $w$。
按照题意,$w$ 为两者的高度差的绝对值。
对集合进行排序,按照 $w$ 进行从小到大排序(Kruskal 部分)。
当我们有了所有排好序的候选边集合之后,我们可以对边进行从前往后处理,每次加入一条边之后,使用并查集来查询「起点」和「终点」是否连通(并查集部分)。
当第一次判断「起点」和「终点」联通时,说明我们「最短路径」的所有边都已经应用到并查集上了,而且由于我们的边是按照「从小到大」进行排序,因此最后一条添加的边就是「最短路径」上权重最大的边。
Java 代码:
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| 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;
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}); } } }
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; } }
|
C++ 代码:
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 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { public: int N = 10009; vector<int> p; int row, col; void unions(int a, int b) { p[find(a)] = find(b); } bool query(int a, int b) { return find(a) == find(b); } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int minimumEffortPath(vector<vector<int>>& heights) { row = heights.size(); col = heights[0].size(); p.resize(row * col); for (int i = 0; i < row * col; ++i) p[i] = i; vector<pair<int, pair<int, int>>> edges; for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { int idx = i * col + j; if (i + 1 < row) { edges.emplace_back(abs(heights[i][j] - heights[i + 1][j]), make_pair(idx, (i + 1) * col + j)); } if (j + 1 < col) { edges.emplace_back(abs(heights[i][j] - heights[i][j + 1]), make_pair(idx, idx + 1)); } } } sort(edges.begin(), edges.end()); int start = 0, end = row * col - 1; for (const auto& edge : edges) { int w = edge.first, a = edge.second.first, b = edge.second.second; unions(a, b); if (query(start, end)) { return w; } } return 0; } };
|
Python 代码:
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 33 34 35 36
| class Solution: def union(self, a: int, b: int) -> None: root_a = self.find(a) root_b = self.find(b) if root_a != root_b: self.p[root_b] = root_a
def query(self, a: int, b: int) -> bool: return self.find(a) == self.find(b)
def find(self, x: int) -> int: if self.p[x] != x: self.p[x] = self.find(self.p[x]) return self.p[x]
def minimumEffortPath(self, heights: List[List[int]]) -> int: self.row = len(heights) self.col = len(heights[0]) self.N = 10009 self.p = list(range(self.row * self.col)) edges = [] for i in range(self.row): for j in range(self.col): idx = i * self.col + j if i + 1 < self.row: edges.append((abs(heights[i][j] - heights[i + 1][j]), (idx, (i + 1) * self.col + j))) if j + 1 < self.col: edges.append((abs(heights[i][j] - heights[i][j + 1]), (idx, idx + 1))) edges.sort(key=lambda x: x[0]) start = 0 end = self.row * self.col - 1 for w, (a, b) in edges: self.union(a, b) if self.query(start, end): return w return 0
|
- 时间复杂度:令行数为 $r$,列数为 $c$,那么节点的数量为 $r \times c$,无向边的数量严格为 $r \times (c - 1) + c \times (r - 1)$,数量级上为 $r \times c$。获取所有的边复杂度为 $O(r \times c)$,排序复杂度为 $O((r \times c)\log{(r \times c)})$,遍历得到最终解复杂度为 $O(r \times c)$。整体复杂度为 $O((r \times c)\log{(r \times c)})$。
- 空间复杂度:使用了并查集数组。复杂度为 $O(r \times c)$。
证明
我们之所以能够这么做,是因为「跳出循环前所遍历的最后一条边必然是最优路径上的边,而且是 $w$ 最大的边」。
我们可以用「反证法」来证明这个结论为什么是正确的。
我们先假设「跳出循环前所遍历的最后一条边必然是最优路径上的边,而且是 $w$ 最大的边」不成立:
我们令循环终止前的最后一条边为 a
假设 a 不在最优路径内:如果 $a$ 并不在最优路径内,即最优路径是由 $a$ 边之前的边构成,那么 $a$ 边不会对左上角和右下角节点的连通性产生影响。也就是在遍历到该边之前,左上角和右下角应该是联通的,逻辑上循环会在遍历到该边前终止。与我们循环的决策逻辑冲突。
$a$ 在最优路径内,但不是 $w$ 最大的边:我们在遍历之前就已经排好序。与排序逻辑冲突。
因此,我们的结论是正确的。a
边必然属于「最短路径」并且是权重最大的边。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1631
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。