§1
题目描述
给定 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)
§2
思路解析动画文字版
记住「dist 记到该格的最小可能最大落差、松弛取 max(dist, 落差)、堆取最小」,下面逐帧套它。
最小体力消耗路径
起点 (0,0)(紫框起点)体力记 0,放进优先队列。中间的 (1,1)=8(红)和四周落差都很大,是要躲开的「高墙」。终点是右下角 (2,2)。
最小体力消耗路径
取出当前体力最小的格 (0,0)(紫,体力 0)并定下来(蓝=已定)。看它四个邻居,尝试用 max(0, 落差) 去刷新更小的体力。
最小体力消耗路径
往下到 (1,0):落差 |1−3| = 2,新体力 = max(0, 2) = 2,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
往右到 (0,1):落差 |1−2| = 1,新体力 = max(0, 1) = 1,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
取出当前体力最小的格 (0,1)(紫,体力 1)并定下来(蓝=已定)。看它四个邻居,尝试用 max(1, 落差) 去刷新更小的体力。
最小体力消耗路径
往下到 (1,1):落差 |2−8| = 6,新体力 = max(1, 6) = 6,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
往右到 (0,2):落差 |2−2| = 0,新体力 = max(1, 0) = 1,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
取出当前体力最小的格 (0,2)(紫,体力 1)并定下来(蓝=已定)。看它四个邻居,尝试用 max(1, 落差) 去刷新更小的体力。
最小体力消耗路径
往下到 (1,2):落差 |2−2| = 0,新体力 = max(1, 0) = 1,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
取出当前体力最小的格 (1,2)(紫,体力 1)并定下来(蓝=已定)。看它四个邻居,尝试用 max(1, 落差) 去刷新更小的体力。
最小体力消耗路径
往下到 (2,2):落差 |2−5| = 3,新体力 = max(1, 3) = 3,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
取出当前体力最小的格 (1,0)(紫,体力 2)并定下来(蓝=已定)。看它四个邻居,尝试用 max(2, 落差) 去刷新更小的体力。
最小体力消耗路径
往下到 (2,0):落差 |3−5| = 2,新体力 = max(2, 2) = 2,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
往右到 (1,1):落差 |3−8| = 5,新体力 = max(2, 5) = 5,比原来的 6 小,更新并入队。
最小体力消耗路径
取出当前体力最小的格 (2,0)(紫,体力 2)并定下来(蓝=已定)。看它四个邻居,尝试用 max(2, 落差) 去刷新更小的体力。
最小体力消耗路径
往右到 (2,1):落差 |5−3| = 2,新体力 = max(2, 2) = 2,比原来的 ∞ 小,更新并入队。
最小体力消耗路径
取出当前体力最小的格 (2,1)(紫,体力 2)并定下来(蓝=已定)。看它四个邻居,尝试用 max(2, 落差) 去刷新更小的体力。
最小体力消耗路径
往右到 (2,2):落差 |3−5| = 2,新体力 = max(2, 2) = 2,比原来的 3 小,更新并入队。
最小体力消耗路径
从队列取出体力最小的是终点 (2,2),体力 2。Dijkstra 第一次定下终点即最优,答案 = 2。
最小体力消耗路径
沿「从谁来的」回溯,绿色就是最优路径:(0,0)→(1,0)→(2,0)→(2,1)→(2,2)。这一路的落差依次是 2、2、2、2,最大是 2,它绕开了中间的 8,把 最大落差压到了最小。这就是答案 2。
边界:单格 0;有等高通路 0;一条线就是其上最大落差。
两个延伸:并查集/二分皆可;它是 minimax 版最短路,松弛用 max。
§3
参考代码
from typing import Listimport heapqclass 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 0看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间：O(mn·log(mn))，每次成功松弛把记录入堆(同一格可能因更小体力多次入堆),网格边数 O(mn),总堆操作 O(mn) 量级、每次 O(log(mn)),整体 O(mn log(mn))
- 空间：O(mn)，dist 矩阵 O(mn),堆最坏也是 O(mn) 量级
§5
易错点
✗ 错误写法：松弛时把落差累加(像普通最短路)
✓ 正确写法：用 max(当前体力, 这一步落差)
代价是「路径上最大的一步」,不是总和;必须取 max 而不是相加
✗ 错误写法：只看一条贪心路径(比如一直往右下)
✓ 正确写法：用 Dijkstra 在所有格子上松弛
最小体力路径可能要绕远(如本题走左下),贪心方向会错过
✗ 错误写法：不跳过堆里的过期记录
✓ 正确写法：e≠dist[r][c] 时跳过
同一格可能多次以不同体力入堆,旧的较大记录要丢弃
§
面试追问把动画讲成自己的话
追问除了 Dijkstra,这题还有哪些解法?
常见三种:① Dijkstra(最直接,本动画用的);② 并查集 + Kruskal 思路:把所有相邻边按落差从小到大加入,每加一条就合并两格,当起点和终点首次连通时,刚加入的那条边的落差就是答案;③ 二分答案 + BFS/DFS:二分一个体力上限 x,检查只走落差 ≤x 的边能否从起点到终点,可达就缩小 x。三者复杂度接近,Dijkstra 和并查集都很常用。
追问这和经典最短路最大的区别是什么?
经典最短路是「路径边权之和最小」,松弛用加法;本题是「路径边权最大值最小」(minimax),松弛用 max。框架(Dijkstra 的取最小、定点、松弛)完全一样,只换了「路径代价怎么合成」这一处。同类的还有「最大化路径上最小值」(maximin)。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 图论套路 39/48
→获取食物的最短路径
LeetCode 1730 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
599道动画图解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路？去图解算法专题