LeetCode 1631中等图/最短路/并查集
最小体力消耗路径 图解题解
这道题到底在问什么
给定 rows×cols 的高度矩阵 heights,从 (0,0) 到 (rows−1,cols−1),每步走相邻格。一条路径的代价是路上相邻格高度差绝对值的最大值。返回最小可能的路径代价。
- 输入
- heights=[[1,2,2],[3,8,2],[5,3,5]]
- 输出
- 2(走左下 1→3→5→3→5,最大落差 2,绕开中间的 8)
最优解：一步一步想明白
- 3记住「dist 记到该格的最小可能最大落差、松弛取 max(dist, 落差)、堆取最小」,下面逐帧套它。
- 4起点 (0,0)(紫框起点)体力记 0,放进优先队列。中间的 (1,1)=8(红)和四周落差都很大,是要躲开的「高墙」。终点是右下角 (2,2)。
- 5取出当前体力最小的格 (0,0)(紫,体力 0)并定下来(蓝=已定)。看它四个邻居,尝试用 max(0, 落差) 去刷新更小的体力。
- 6往下到 (1,0):落差 |1−3| = 2,新体力 = max(0, 2) = 2,比原来的 ∞ 小,更新并入队。
- 7往右到 (0,1):落差 |1−2| = 1,新体力 = max(0, 1) = 1,比原来的 ∞ 小,更新并入队。
- 8取出当前体力最小的格 (0,1)(紫,体力 1)并定下来(蓝=已定)。看它四个邻居,尝试用 max(1, 落差) 去刷新更小的体力。
- 9往下到 (1,1):落差 |2−8| = 6,新体力 = max(1, 6) = 6,比原来的 ∞ 小,更新并入队。
- 10往右到 (0,2):落差 |2−2| = 0,新体力 = max(1, 0) = 1,比原来的 ∞ 小,更新并入队。
- 11取出当前体力最小的格 (0,2)(紫,体力 1)并定下来(蓝=已定)。看它四个邻居,尝试用 max(1, 落差) 去刷新更小的体力。
- 12往下到 (1,2):落差 |2−2| = 0,新体力 = max(1, 0) = 1,比原来的 ∞ 小,更新并入队。
- 13取出当前体力最小的格 (1,2)(紫,体力 1)并定下来(蓝=已定)。看它四个邻居,尝试用 max(1, 落差) 去刷新更小的体力。
- 14往下到 (2,2):落差 |2−5| = 3,新体力 = max(1, 3) = 3,比原来的 ∞ 小,更新并入队。
- 15取出当前体力最小的格 (1,0)(紫,体力 2)并定下来(蓝=已定)。看它四个邻居,尝试用 max(2, 落差) 去刷新更小的体力。
- 16往下到 (2,0):落差 |3−5| = 2,新体力 = max(2, 2) = 2,比原来的 ∞ 小,更新并入队。
- 17往右到 (1,1):落差 |3−8| = 5,新体力 = max(2, 5) = 5,比原来的 6 小,更新并入队。
- 18取出当前体力最小的格 (2,0)(紫,体力 2)并定下来(蓝=已定)。看它四个邻居,尝试用 max(2, 落差) 去刷新更小的体力。
- 19往右到 (2,1):落差 |5−3| = 2,新体力 = max(2, 2) = 2,比原来的 ∞ 小,更新并入队。
- 20取出当前体力最小的格 (2,1)(紫,体力 2)并定下来(蓝=已定)。看它四个邻居,尝试用 max(2, 落差) 去刷新更小的体力。
- 21往右到 (2,2):落差 |3−5| = 2,新体力 = max(2, 2) = 2,比原来的 3 小,更新并入队。
- 22从队列取出体力最小的是终点 (2,2),体力 2。Dijkstra 第一次定下终点即最优,答案 = 2。
- 23沿「从谁来的」回溯,绿色就是最优路径:(0,0)→(1,0)→(2,0)→(2,1)→(2,2)。这一路的落差依次是 2、2、2、2,最大是 2,它绕开了中间的 8,把「最大落差」压到了最小。这就是答案 2。
⚠️ 容易写错的地方
✗ 错：松弛时把落差累加(像普通最短路)
✓ 对：用 max(当前体力, 这一步落差)
代价是「路径上最大的一步」,不是总和;必须取 max 而不是相加
✗ 错：只看一条贪心路径(比如一直往右下)
✓ 对：用 Dijkstra 在所有格子上松弛
最小体力路径可能要绕远(如本题走左下),贪心方向会错过
✗ 错：不跳过堆里的过期记录
✓ 对：e≠dist[r][c] 时跳过
同一格可能多次以不同体力入堆,旧的较大记录要丢弃
完整代码（Python / C++ / Java）
Python
from typing import List
import heapq
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
dist = [[10**18] * n for _ in range(m)]
dist[0][0] = 0
heap = [(0, 0, 0)]
while heap:
effort, r, c = heapq.heappop(heap)
if (r, c) == (m - 1, n - 1):
return effort
if effort != dist[r][c]:
continue
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
ne = max(effort, abs(heights[r][c] - heights[nr][nc]))
if ne < dist[nr][nc]:
dist[nr][nc] = ne
heapq.heappush(heap, (ne, nr, nc))
return 0C++
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
using T = tuple<int,int,int>;
priority_queue<T, vector<T>, greater<T>> pq;
dist[0][0] = 0; pq.push({0,0,0});
int dirs[5] = {1,0,-1,0,1};
while (!pq.empty()) {
auto [effort, r, c] = pq.top(); pq.pop();
if (r == m - 1 && c == n - 1) return effort;
if (effort != dist[r][c]) continue;
for (int d = 0; d < 4; ++d) {
int nr = r + dirs[d], nc = c + dirs[d+1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int ne = max(effort, abs(heights[r][c] - heights[nr][nc]));
if (ne < dist[nr][nc]) { dist[nr][nc] = ne; pq.push({ne, nr, nc}); }
}
}
}
return 0;
}
};Java
import java.util.*;
class Solution {
public int minimumEffortPath(int[][] heights) {
int m = heights.length, n = heights[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
dist[0][0] = 0; pq.offer(new int[]{0,0,0});
int[] dirs = {1,0,-1,0,1};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[1] == m - 1 && cur[2] == n - 1) return cur[0];
if (cur[0] != dist[cur[1]][cur[2]]) continue;
for (int d = 0; d < 4; d++) {
int nr = cur[1] + dirs[d], nc = cur[2] + dirs[d + 1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
int ne = Math.max(cur[0], Math.abs(heights[cur[1]][cur[2]] - heights[nr][nc]));
if (ne < dist[nr][nc]) { dist[nr][nc] = ne; pq.offer(new int[]{ne, nr, nc}); }
}
}
}
return 0;
}
}复杂度
时间
O(mn·log(mn))
每次成功松弛把记录入堆(同一格可能因更小体力多次入堆),网格边数 O(mn),总堆操作 O(mn) 量级、每次 O(log(mn)),整体 O(mn log(mn))
空间
O(mn)
dist 矩阵 O(mn),堆最坏也是 O(mn) 量级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最小体力消耗路径 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
除了 Dijkstra,这题还有哪些解法?+
常见三种:① Dijkstra(最直接,本动画用的);② 并查集 + Kruskal 思路:把所有相邻边按落差从小到大加入,每加一条就合并两格,当起点和终点首次连通时,刚加入的那条边的落差就是答案;③ 二分答案 + BFS/DFS:二分一个体力上限 x,检查只走落差 ≤x 的边能否从起点到终点,可达就缩小 x。三者复杂度接近,Dijkstra 和并查集都很常用。
这和经典最短路最大的区别是什么?+
经典最短路是「路径边权之和最小」,松弛用加法;本题是「路径边权最大值最小」(minimax),松弛用 max。框架(Dijkstra 的取最小、定点、松弛)完全一样,只换了「路径代价怎么合成」这一处。同类的还有「最大化路径上最小值」(maximin)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最小体力消耗路径 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。