Appearance
19 最小体力消耗路径：如何突破经典题型，掌握解题模板？
今天我们继续从多个角度去求解一个题目，尝试运用丰富的解题工具，比如我们的"老熟人"BFS/DFS/Dijkstra 算法，帮助你巩固和应用已经学习过的知识点。除此之外，本讲还会重点介绍一些在"一题多解"中尚未覆盖到的算法：
并查集
二分搜索
动态规划（Bellman-Ford 算法）
通过"一题多解"的训练，拓展我们的思维，一起去探索"五彩缤纷"的解题技巧。让我们马上开始。
题目
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。
一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
你每次可以往 上、下、左、右四个方向之一移动，你想要找到耗费体力最小的一条路径。
一条路径耗费的体力值 是由路径上相邻格子之间高度差绝对值 的最大值 决定的。请你返回从左上角走到右下角的最小体力消耗值 。矩阵中最大值不超过 10^6^。
例如给定如下地图：
输入：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)。因此，这里我们需要使用并查集来判断出发点与终点的连通性。
至此，我们可以写出伪代码如下：
java
edges = getAllEdges();
sort(edges);
for edge in edges:
addEdge(edge);
if (connected(start, endNode)):
return edge.cost;有了以上的思路，我们就可以写出并查集的求解代码了（解析在注释里）：
java
// 并查集类
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;
}
}复杂度分析：一个 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 函数
根据前面四步分析法，我们已经可以写出二分搜索的伪代码了：
java
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)）。
如果再算上最外层二分搜索的时间复杂度，由于最大的数为 10^6^，所以整个二分搜索的时间复杂度为：
O(lg(10^6^) N x M) ← 二分 + BFS/DFS；
或者 O(lg(10^6^) N x M x lg (N x M)) ← 二分 + 并查集。
基于这样的思路，我们就可以写出二分搜索的代码了（二分搜索 + DFS）：
java
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;
}
}复杂度分析 ：时间复杂度O(lg(10^6^) N x M)，空间复杂度为O(N x M)。
练习题 1：在文中，我们已经证明了这道题还可以使用二分搜索 + BFS / 并查集来解决。你能写一下代码吗？
特点 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 算法的代码了（解析在注释里）：
java
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 算法做度量函数的微调，调整之后的代码如下（解析在注释里）：
java
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];
}
}写完代码之后，我们再考虑一下 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 算法解决这道题目了。代码如下：
java
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];
}
}复杂度分析：当给定图为 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 的总和最小。
你可以自己尝试求解这道题目，把答案写在留言区，我们一起讨论。关于最小体力消耗题目就介绍到这里。接下来，下一讲介绍"20 | 5 种解法，如何利用常量空间求解最长有效括号长度？"，让我们继续前进。
附录：题目出处和代码汇总
| 题目 | 测试平台 | 并查集：Java/C++/Python 二分 + DFS：Java/C++/Python 二分 + BFS：Java/C++/Python 二分 + 并查集：Java/C++/Python BF 算法：Java/C++/Python Dijkstra 算法：Java/C++/Python |
|---|---|---|
| 思考题 | 测试平台 | 代码：Java/C++/Python |