今天我们继续从多个角度去求解一个题目，尝试运用丰富的解题工具，比如我们的“老熟人”BFS/DFS/Dijkstra 算法，帮助你巩固和应用已经学习过的知识点。除此之外，本讲还会重点介绍一些在“一题多解”中尚未覆盖到的算法：
并查集
二分搜索
动态规划（Bellman-Ford 算法）
通过“一题多解”的训练，拓展我们的思维，一起去探索“五彩缤纷”的解题技巧。让我们马上开始。
题目
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。
一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
你每次可以往 上、下、左、右四个方向之一移动，你想要找到耗费体力最小的一条路径。
一条路径耗费的体力值是由路径上相邻格子之间高度差绝对值的最大值决定的。请你返回从左上角走到右下角的最小体力消耗值 。矩阵中最大值不超过 106。
例如给定如下地图：
输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
注意：我们在处理这个题目的时候，一定要注意题目要求的结果是：
从左上角走到右下，路径上高度差绝对值的最大值要最小。
即不是求路径和，也不是求最短路径。
预处理
当拿到这个题之后，我们发现，与脑海里熟悉的题目还是有点差异的。因此需要对题目进行一些预处理，尽量将题目转换成为我们熟悉的题目。
点的处理
首先，如果我们把矩阵中的每个位置都当成一个图（算法中的图 Graph）中的一个点。那么可以将点表示如下：
这里，为了表示方便，我们将每个点独立进行编号。当然，这种编号只是为了方便我们索引每个点的具体信息。
如果我们想用一维数组存放点的信息，就需要将点编号为一维的整数。如果我们想用二维数组存放点的信息，就需要用 <row, col> 来表示一个点的编号。
至于使用一维数组还是二维数组，要根据具体的算法和题目进行分析。我们来看下面两种情况。
因为我们平常使用的并查集便是在一维数组上操作，那么把点编号为一维的整数无疑更方便。
DFS/BFS 遍历的时候，对于矩阵而言，二维的信息遍历时更方便，因此搜索时，我们经常使用 <row, col> 来表示一个点的编号。
边的处理
通常图的题目，都会直接给出边的 <出发点，终点，权重>，但是这道题却没有直接给出来。当然，在“18 | 单词接龙：如何巧用深搜与广搜的变形？”中，我们也遇到过没有直接给出边的信息的情况。当时的处理方式是采用“预处理”挖掘出图中边的信息。
于是，需要我们把这边的信息给挖掘出来。那么，在这个题中，边的信息是什么？根据题目的定义，当我们从结点 A<r 行,c 列> 走到结点 B<nr 行, nc 列> 的时候，消耗的体力值是：
Math.abs(heights[r][c] - heights[nr][nc])
因此，边可以表示为：
edge = [<r,c> <nr,nc>, cost]cost = Math.abs(heights[r][c] - heights[nr][nc])
加上边之后，图问题就可以表示如下：
根据上述分析，题目就可以转换成我们非常熟悉的题目：
给定图的点和边，以及出发点和终点，找出一条路径，使得这条路径上边的权重的最大值尽可能最小。输出这个最小值。
特点 1：连通性
题目要求找一个最小的值 ans，并且出发点和终点必须在一条路径上，这条路径上所有的边的权重都 <= ans。
那么反过来说，如果我们把权重大于 ans 的边都删除，出发点与终点的这条路径仍然是存在的。
既然如此，那么我们采用如下动图所示的方式应该也可以工作：
通过这种方式，我们需要解决的问题，可以表示如下：
取出所有的边，并且按权重排序（因为我们要按权重加入图）；
当加入一条边之后，我们需要查看一下图中的两点是否连通。
其中第一个问题比较容易处理。现在问题的核心与重点就是需要尽快判断两个点是否连通。
根据我们之前学过的知识，判断图中两个点是否连通，可以使用：
并查集
BFS
DFS
但是，BFS/DFS 如果需要每加入一条边都进行判断，很明显是不适合的。当有一个 N x N 的矩阵，每次 BFS/DFS 的时间复杂度为 O(N x N)，整个算法的时间复杂度就达到 O(E x N x N)。
那么只能使用并查集，因为我们知道，并查集检查两个点是否连通的时候，时间杂度可以达到 O(lgN)。因此，这里我们需要使用并查集来判断出发点与终点的连通性。
至此，我们可以写出伪代码如下：
1
2
3
4
5
6
|
edges = getAllEdges();
sort(edges);
for edge in edges:
addEdge(edge);
if (connected(start, endNode)):
return edge.cost;
|
有了以上的思路，我们就可以写出并查集的求解代码了（解析在注释里）：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
// 并查集类
class UnionFind {
private int[] F = null;
public UnionFind(int n) {
Init(n);
}
private void Init(int n) {
F = new int[n];
for (int i = 0; i < n; i++) {
F[i] = i;
}
}
public int Find(int x) {
if (x == F[x]) {
return x;
}
F[x] = Find(F[x]);
return F[x];
}
public void Union(int x, int y) {
F[Find(x)] = Find(y);
}
}
class Solution
{
// 行数
private int Rows = 0;
// 列数
private int Cols = 0;
// 四个方向
private int[][] dir = { { 0, 1 }, { 0, -1 },
{ 1, 0 }, { -1, 0 } };
// 由于并查集是一维的，我们需要将二维的点映射到
// 一维的点
private int getPointMapping(int r, int c) {
return r * Cols + c;
}
// 这个函数并不是把edge加到图中，而是在收集一条边
// edge: startNode = <r,c>, toNode=<nr,nc>, cost
// 加入边数组中
private void putEdge(int[][] edges,
int iter,
int r, int c,
int nr, int nc,
int cost) {
edges[iter][0] = getPointMapping(r, c);
edges[iter][1] = getPointMapping(nr, nc);
edges[iter][2] = cost;
}
// 处理的主函数
public int minimumEffortPath(int[][] heights) {
if (heights == null || heights[0] == null) {
return 0;
}
// 收集行数
Rows = heights.length;
// 收集列数
Cols = heights[0].length;
// 如果只有一个点
if (Rows == 1 && Cols == 1) {
return 0;
}
// 采用并查集的做法
// 横向的无向边的数目
final int hNumber = Rows * (Cols - 1);
// 纵向的无向边的数目
final int vNumber = Cols * (Rows - 1);
// 无向边
// 记录起点，终点，权重
int[][] edges = new int[hNumber + vNumber][3];
// 得到所有的边
int edgeIter = 0;
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
// 看一下 右边的点
if (c + 1 < Cols) {
// 得到边的权重
int edgeCost =
Math.abs(heights[r][c] - heights[r][c + 1]);
// 将边放到边集中
putEdge(edges, edgeIter,
r, c, r, c + 1, edgeCost);
edgeIter++;
}
if (r + 1 < Rows) {
// 得到一条向下的边的权重
int edgeCost =
Math.abs(heights[r][c] - heights[r + 1][c]);
// 将边放到边集中
putEdge(edges, edgeIter,
r, c, r + 1, c, edgeCost);
edgeIter++;
}
}
}
// 再将边进行排序
Arrays.sort(edges, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
});
// 排序结束之后，再使用并查集，依次加入边
final int totalNodes = Rows * Cols;
// 并查集
UnionFind uf = new UnionFind(totalNodes);
final int src = 0;
final int dst = getPointMapping(Rows - 1, Cols - 1);
for (int[] edge : edges) {
uf.Union(edge[0], edge[1]);
// 如果能让 src dst连通
// 那么就是当前的cost
if (uf.Find(src) == uf.Find(dst)) {
return edge[2];
}
}
assert 0 > -1; // Should not reach here!
return 0;
}
}
|
代码：Java/C++/Python
复杂度分析：一个 N x M 的数组，可以认为一共有 O(N x M) 条边，收集到这些边之后，然后进行排序，排序的时间复杂度为 O(N x M x lg(N x M))，存放边的空间复杂度为 O(N x M)。接下来，我们需要利用并查集进行处理，一共有 O(N x M) 个点，O(N x M) 条边。那么并查集处理的时间复杂度为 O(N x M x lg(N x M))。所以，整个问题时间复杂度为 O(N x M x lg(N x M))，空间复杂度为 O(N x M)。
当你看完这个题，你还可以回过头去看看“07 | 并查集：如何利用两行代码写并查集？”里面的例 1，在那里，我们同样用到了相同的方法进行处理——最小生成树的思想。通过这些比较，可以发现我们可以通过掌握一种算法思想，在不同的题目中游刃有余。
特点 2：最小值
我们再回到题目，题目要求的是最小值。那么我们想一想：最小值 ans 肯定是一个分界，这个分界体现在两个方向：
比 ans 更小的值，不会让出发点和终点之间可以连通；
大于等于 ans 的值，那么肯定可以让出发点与终点可以连通。
如果我们用数组进行表示，那么可以达到如下图所示的效果：
如果我们分别用 -1 表示 NO，0 表示 OK。那么问题转变成下面这样：
我们需要在一个左边为 -1，右边为 0 的数组中，找到第一个为 0 的下标的位置。那么，最适合解决这个问题的算法就是二分搜索了。
四步法
现在算法方向已经确定了，是时候拿出我们的“二分搜索四步法”了。如果你对这个方法还不太熟悉，可以先回到“09 | 二分搜索：为什么说有序皆可用二分？”复习一下二分搜索的内容，再来看接下来的分析。
第一步：要什么，什么就是 x。
第二步：满足约束条件的 f(x) = 0。
第三步：不满足约束条件的 f(x) 设置为 -1 或者 1。
第四步：最优解 0 在 C[] 的最左边还是最右边，决定使用 lowerBound 还是 upperBound。
接下来，我们一步一步展开。
第一步
我们的问题是要输出一个最小体力消耗值，也就是 x。确定 x 之后，我们还需要确定 x 的范围。在这个题中，所有的边都加上之后，出发点与终点是肯定有路径的。所以 x 的范围就确定了：
x 的最小值，就是图中边的权重的最小值
x 的最大值，就是图中边的权重的最大值
第二步
这里需要确定 f(x) = 0。根据题意，当我们得到最小消耗的体力值 x 之后，在遍历图的时候，当发现边的权重大于 x，直接把这条边禁用即可。当发现出发点与终点之间存在通路，我们就可以认为 f(x) = 0。
第三步
得到最小消耗体力值 x 之后，在遍历时，把权重大于 x 的边禁用，如果发现出发点与终点之间不存在通路，此时设置 f(x) = -1。
在这个题中，由于出发点与终点只有连通与不连通两种情况。所以我们“二分搜索”映射之后的数组里面只会有 -1 和 0。
第四步
在本题中，当映射到一个数组之后，我们要求的是满足 f(x) = 0 的最小值。
也就是求数组中值为 0 的第一个下标，那么肯定应该使用 lowerBound。
f 函数
根据前面四步分析法，我们已经可以写出二分搜索的伪代码了：
1
2
3
4
5
6
7
8
9
|
l = minCost
r = maxCost
while l < r:
mid = l + ((r-l)>>1) // mid表示x
mv = f(mid) // 调用f(x)
if (mv < 0):
l = mid + 1
else:
r = mid
|
不过在正式写代码之前，还是要想一下 f 函数如何写。我们可以先回想一下 f(x) 要解决的问题：
禁用所有权重大于 x 的边之后，图中出发点与终点之间是否还有路径。
我们可以把禁用权重大于 x 的边，看成是利用一个旧图，生成了一张新图。比如：
那么 f(x) 的本质就是在一个新图上判断两点之间的连通性。关于连通性的判定，我们前面提到过，有 3 种办法：
并查集
BFS
DFS
在特点 1 中，我们说明了只能选用并查集，不能使用 BFS 与 DFS，还给出了时间复杂度上的证明。在这里，恰恰相反，三种办法都是可以使用的。下面我们一起证明一下。
假设给定了 N x M 大小的矩阵。
并查集：一共有 O(N x M) 条边，时间复杂度主要由并查集的 Union 决定，一共需要 Union O(N x M) 次，每次 Union 时间复杂度为 O(lg(N x M)（因为一共有 O(N x M) 个点）。所以总共的时间复杂度为 O(N x M lg(N x M))。
BFS：一共有 O(N x M) 个点，最差情况下，每个点都会遍历，所以时间复杂度为 O(N x M)。
DFS：一共有 O(N x M) 个点，最差情况下，每个点都会遍历，所以时间复杂度为 O(N x M)。
也就是说，f(x) 函数的时间复杂度都差不多（并查集多了一个 O(lg)）。
如果再算上最外层二分搜索的时间复杂度，由于最大的数为 106，所以整个二分搜索的时间复杂度为：
O(lg(106) N x M) ← 二分 + BFS/DFS；
或者 O(lg(106) N x M x lg (N x M)) ← 二分 + 并查集。
基于这样的思路，我们就可以写出二分搜索的代码了（二分搜索 + DFS）：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
class Solution {
// 二分搜索
// 行数
private int Rows = 0;
// 列数
private int Cols = 0;
// 一个点周围的四个方向
int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
boolean[][] vis = null;
private void clearVisRecord()
{
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
vis[r][c] = false;
}
}
}
// 这里采用DFS来寻路
// <r,c>是当前的出发点
private boolean dfs(int[][] heights, int maxValue,
int r, int c) {
// 如果已经走到了目标点<rows-1, cols-1>
if (r == Rows - 1 && c == Cols - 1) {
return true;
}
// 查看 <r,c>点的四周
for (int d = 0; d < 4; d++) {
final int nr = r + dir[d][0];
final int nc = c + dir[d][1];
// 如果周边的点有效，并且没有被访问过
if ((!(nr < 0 || nc < 0 || nr >= Rows || nc >= Cols))
&& !vis[nr][nc]) {
// 获取边的代价
final int cost =
Math.abs(heights[r][c] - heights[nr][nc]);
// 在走的时候，如果比midValue大，那么这条路就不能走了
if (cost <= maxValue) {
vis[nr][nc] = true;
if (dfs(heights, maxValue, nr, nc)) {
return true;
}
}
}
}
return false;
}
// f(x)函数
// 重新映射之的一维数组
// midValue是在二分的时候给定的值
// 我们在进行搜索的时候，路径上的绝对值不能比这个大
// 只能是 <= midValue.
// 此时我们只需要寻找看看是否存在一条路径即可
// 如果存在一条路径，上面的绝对值 <= midValue
// 那么满足条件-> 返回0
// 如果没有这样的路径，那么返回-1
private int getC(int[][] heights, int midValue) {
clearVisRecord();
vis[0][0] = true;
return dfs(heights, midValue, 0, 0) ? 0 : -1;
}
public int minimumEffortPath(int[][] heights) {
if (heights == null || heights[0] == null) {
return 0;
}
Rows = heights.length;
Cols = heights[0].length;
// if just one node
if (Rows == 1 && Cols == 1) {
return 0;
}
// 生成vis数组
vis = new boolean[Rows][Cols];
// 二分搜索
// 找到搜索范围里：最大值/最小值
int minCost = Integer.MAX_VALUE;
int maxCost = 0;
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
// 看一下 右边的点
if (c + 1 < Cols) {
int rightValue =
Math.abs(heights[r][c] - heights[r][c + 1]);
minCost = Math.min(minCost, rightValue);
maxCost = Math.max(maxCost, rightValue);
}
if (r + 1 < Rows) {
int downValue =
Math.abs(heights[r][c] - heights[r + 1][c]);
minCost = Math.min(minCost, downValue);
maxCost = Math.max(maxCost, downValue);
}
}
}
// 那么应该有一个值 target
// 当 路径的最大绝对值差为 x
// 并且 x >= target的时候
// 总是可以走通的
// 所以我们二分搜索的范围就为[minCost, maxCost + 1)
// 我们定义-1: 表示左上角与右下有没有通路
// 0: 表示左上角与右下角有通路
// 那么形成的C数组就是[-1,-1,-1,-1, 0, 0, 0, 0]
// 这样的结构
// 因此，我们在利用二分搜索的时候，只需要找到最左边的
// 0的位置就可以了。
int l = minCost, r = maxCost + 1;
while (l < r) {
final int mid = l + ((r - l) >> 1);
final int mv = getC(heights, mid);
if (mv < 0) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度O(lg(106) N x M)，空间复杂度为O(N x M)。
练习题 1：在文中，我们已经证明了这道题还可以使用二分搜索 + BFS / 并查集来解决。你能写一下代码吗？
二分 + BFS：Java/C++/Python二分 + 并查集：Java/C++/Python
特点 3：再看最小值
谈到图中两点之间路径的最小值，有没有觉得很熟悉？我们在“18 | 单词接龙：如何巧用深搜与广搜的变形？”中刚刚介绍过“求解两个点的最短路径”的方法：
两点之间的最短路径（BFS 算法/Dijkstra 算法/BF 算法，即 Bellman-Ford 算法）；
一个点到其他所有点的最短路径（Dijkstra 算法/BF 算法）；
每两点之间的最短路径（Floyd 算法）。
在这里，一个点到其他所有点的最短路径当然是包含了“两点之间的最短路径”的情况。所以后面我们在讨论的时候，都是一个点到其他所有点的最短路径场景下的 BF 算法。
下面尝试一下 BF 算法（我们讲的场）。在“18 | 单词接龙：如何巧用深搜与广搜的变形？”的“练习题 1”里提到了可以用 BF 算法进行求解，但是没有详细介绍如何用 BF 算法。这里我们详细介绍一下。
如果直接看BF 算法的代码，容易看得一头雾水，但其实这是一种比较容易理解的算法。在拿出BF算法的模板代码前，我们先讲一下这个算法的本质（下图中橙色点表示出发点）。注意：是本质！并不完全是一个计算过程的模拟。
Step 0. 首先我们有一些离散的点， 此时还没有加入任何边。
Step 1. 把所有的边加入图中。只有一部分点（绿色）会在这一轮迭代中得到最终的src 出发的最短路径。
注意：有一些点，经过这一轮的操作之后，虽然会与出发点 src 连通，但并没有得到最终最短路径，在图中我们就没有画出这些点与 src 的连线。
此时，我们可以再次从绿色点（因为它们已经是最终的最短路径了）出发，如果再次利用所有的边，应该可以再更新一波，得到一些新的最短路径的点。
Step 2. 再次把所有的边加入图中，得到第二波最短路径的点（紫色）。
Step 3: 如果我们再从紫色点出发，把所有的边加到图中，那么可以得到最后一波最短路径的点（红色）。
这里只是假设更新 3 次就结束了，实际上有可能更多。那么问题来了，到底要把所有的边用来更新多少次呢？
这里可以有两种办法。
积极的办法：当发现不能更新出一波新的最短路径的点的时候，就应该停止了。
消极的办法：假设每一波最差情况下只有一个点得到了最终的最短路径，那么一共需要更新 N-1 轮（在有 N 个点的情况下）。
那么问题的时间复杂度为 O(E x N)，其中 E 为边的数目，N 表示最差情况下更新的次数。
基于这种思想，我们就可以写出 BF 算法的代码了（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
|
for (var i = 0; i < n - 1; i++) {
for (var j = 0; j < m; j++) {
//对m条边进行循环
var edge = edges[j];
// 松弛操作
if(distance[edge.to] >
distance[edge.from] + edge.weight ) {
distance[edge.to] = distance[edge.from] + edge.weight;
}
}
}
|
不过，要解决本题，还需要注意，经典的 BF 算法的最短路径是最小路径和为度量的，而在本题中，是以一条路径上的最大权重进行度量的，所以我们还需要对 BF 算法做度量函数的微调，调整之后的代码如下（解析在注释里）：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
class Solution {
// 行数
private int Rows = 0;
// 列数
private int Cols = 0;
// 一个点周围的四个方向
int[][] dir = { { 0, 1 }, { 0, -1 },
{ 1, 0 }, { -1, 0 } };
public int minimumEffortPath(int[][] heights) {
if (heights == null || heights[0] == null) {
return 0;
}
Rows = heights.length;
Cols = heights[0].length;
// 如果只有一个结点
if (Rows == 1 && Cols == 1) {
return 0;
}
// 采用BF算法
// 从左上角走到右下角，最多只需要走Rows + Cols次
// 所以我们在更新的时候，最多只需要更新Rows + Cols次
// 并且，在更新的过程中，如果我们发现，没有任何一个点被更新的时候
// 我们就可以退出来了
final int maxDist = Integer.MAX_VALUE >> 4;
int[][] dist = new int[Rows][Cols];
// 初始化整个距离
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
dist[r][c] = maxDist;
}
}
dist[0][0] = 0;
final int maxUpdateTimes = Rows + Cols;
// 用BF算法来更新
for (int updateTimes = 0;
updateTimes < maxUpdateTimes; updateTimes++) {
boolean hasUpdateItem = false;
// 用所有的边来进行更新
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
for (int d = 0; d < 4; d++) {
int nr = r + dir[d][0];
int nc = c + dir[d][1];
if (!(nr < 0 || nc < 0 ||
nr >= Rows || nc >= Cols)) {
// 拿到边的代价
final int cost =
Math.abs(heights[r][c] - heights[nr][nc]);
// 这条路径走过来的最大代价
final int nextCost = Math.max(dist[r][c], cost);
if (nextCost < dist[nr][nc]) {
dist[nr][nc] = nextCost;
hasUpdateItem = true;
}
}
}
}
}
// 如果没有更新
if (!hasUpdateItem) {
break;
}
}
return dist[Rows - 1][Cols - 1];
}
}
|
代码：Java/C++/Python
写完代码之后，我们再考虑一下 BF 算法与 Dijkstra 算法的联系与区别。
联系：BF 算法与 Dijkstra 算法都会用更小的“最短路径”来更新。
区别：BF 算法属于动态规划算法，而 Dijkstra 算法则是属于贪心算法。
1）相对来说，BF 算法在每一轮的更新中，都会得到一波点，这些点有最终的最短路径。但是更新的时候，需要用到所有的边。
2）Dijkstra 算法在更新点的距离时，则是从点的角度出发。既然每一波点都会得到最短距离，那么我就利用这波点去更新别的点的最短距离。
特点 4: 又看最小值
谈到图中两点之间关于路径的最小值。在“第 18 讲”中我们讲过，在求两个点的最短路径的时候，可以有 3 种情况：两点最短、点与其他点最短路径、每两点之间的最短路径。我们接触的最短路径的题目中，很多题目都是将“最短”定义为：
一条路径上所有边的权重之和，要最小！
但是，在本题中却不是这样，我们要求的是：
一条路径上所有边的权重的最大值，要最小！
那么，当这个“最短”定义发生变化的时候，我们是否还可以使用 BFS/Dijkstra/BF 算法呢？
这里我们先回顾一下原始 Dijkstra 算法。
在 Dijkstra 算法中，我们需要用一个 dist 数组来记录“最短路径”和。
当出发点 src 走到点 x，导致 dist[x] 有更新的时候，那么点 x 还可以走到它周围的点，进一步更新周围的点。因此，需要将点 x 放到一个优先级队列中。
每次从优先级队列中取出最值得更新的点，作为出发点，用来更新其周围的点。
如果将 Dijkstra 算法迁移到这个题目，我们只需要改变 dist[] 数组的含义就可以了。
原始的 Dijkstra 算法的 dist[x] 表示：从出发点 src 走到点 x 的最小路径和。
本题的 Dijkstra 中的 dist[x] 的含义：从出发点 src 走到点 x 路径上边的权重的最大值。
基于这个微小的改动，我们就可以利用 Dijkstra 算法解决这道题目了。代码如下：
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
61
62
63
64
65
66
67
68
69
70
71
72
|
class Solution {
// 行数
private int Rows = 0;
// 列数
private int Cols = 0;
// 四个方向
private int[][] dir = { { 0, 1 }, { 0, -1 },
{ 1, 0 }, { -1, 0 } };
public int minimumEffortPath(int[][] heights) {
if (heights == null || heights[0] == null) {
return 0;
}
Rows = heights.length;
Cols = heights[0].length;
// 设置矩阵的最大距离
final int maxDist = Integer.MAX_VALUE >> 4;
int[][] dist = new int[Rows][Cols];
for (int r = 0; r < Rows; r++) {
for (int c = 0; c < Cols; c++) {
dist[r][c] = maxDist;
}
}
dist[0][0] = 0;
// java小堆
Queue<int[]> Q =
new PriorityQueue<>((v1, v2) ->
dist[v1[0]][v1[1]] - dist[v2[0]][v2[1]]);
// 放入出发点
Q.offer(new int[] { 0, 0 });
while (!Q.isEmpty()) {
// 取出最近的点
int[] topNode = Q.poll();
final int r = topNode[0];
final int c = topNode[1];
// 我们看一下这个点四周的点
for (int d = 0; d < 4; d++) {
// 找到周边的下一个点
final int nr = r + dir[d][0];
final int nc = c + dir[d][1];
// 看一下这个点的权重是否会更新
if (!(nr < 0 || nc < 0 || nr >= Rows || nc >= Cols)) {
// 如果要走过去的点是合法的点
// 点之间的边上的权重
// 是由点与点之间的abs()决定的
final int weight =
Math.abs(heights[r][c] - heights[nr][nc]);
// 注意，题目要求是取整条路径上的绝对值的最大值
final int nextDist = Math.max(dist[r][c], weight);
if (nextDist < dist[nr][nc]) {
dist[nr][nc] = nextDist;
Q.offer(new int[] { nr, nc });
}
}
}
}
return dist[Rows - 1][Cols - 1];
}
}
|
代码：Java/C++/Python
复杂度分析：当给定图为 N x M 时，时间复杂度为 O(N x M x lg(N x M))，空间复杂度最差情况下，所有的元素都在队列中 O(N x M)。
总结
在这一讲中，我们通过题目两方面的特点：连通性、最小值展开，介绍了以下算法：
并查集
二分搜索
动态规划
Dijkstra 算法
这里我将这些知识点浓缩在一张思维导图里面，有助于帮助你总结和复习。
思考题
给定一个包含非负整数的
m x n
网格
grid
，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明： 每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
代码：Java/C++/Python
你可以自己尝试求解这道题目，把答案写在留言区，我们一起讨论。关于最小体力消耗题目就介绍到这里。接下来，下一讲介绍“20 | 5 种解法，如何利用常量空间求解最长有效括号长度？”，让我们继续前进。
附录：题目出处和代码汇总
题目
测试平台
并查集：Java/C++/Python二分 + DFS：Java/C++/Python二分 + BFS：Java/C++/Python二分 + 并查集：Java/C++/PythonBF 算法：Java/C++/PythonDijkstra 算法：Java/C++/Python
思考题
测试平台
代码：Java/C++/Python
-– ### 精选评论