题目描述
思路解析动画文字版
按普通最短步数走会忽略高度瓶颈。
把路径代价定义为一路上的最大高度，用小根堆每次扩展当前最小瓶颈路径。
1. 代价 = 路径上的最高水位：t = 从起点到某格、路径上的最高水位。用小根堆每次弹出 t 最小的格子扩展(Dijkstra 变体)。起点 (0,0) t=0。灰格是 8、9 的高墙。
2. 取堆顶 t 最小 → 确认 (0,1)：起点四周入堆：(0,1) 需 t=max(0,1)=1，(1,0) 需 t=max(0,8)=8。堆顶 t=1 最小 → 确认 (0,1)。
3. 继续弹 t=1 → 确认 (1,1)：从 (0,1) 扩展：(1,1) 需 t=max(1,1)=1；(0,2)=9 这种高墙 t 巨大、沉到堆底。继续弹 t=1 → 确认 (1,1)。
4. → 确认 (2,1)，t 仍 = 1：继续沿 t=1 的格子走，确认 (2,1)。
5. 关键帧 · 第一次弹出终点 = 答案：关键帧：第一次从堆里弹出终点 (2,2)，此时 t=1 → 答案 1。Dijkstra 保证：第一次弹出终点的 t，就是所有路径里「最高水位的最小值」。全程绕开了 8、9 的高地。
一句话记住：把路径代价定义为一路上的最大高度，用小根堆每次扩展当前最小瓶颈路径。
边界三连：三种边界先想清楚。
面试追问 1：核心思路。
面试追问 2：复杂度分析。
面试追问 3：二分/并查集替代解法。
这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
参考代码
class Solution: def swimInWater(self, grid): import heapq n = len(grid) heap = [(grid[0][0], 0, 0)] seen = {(0, 0)} while heap: t, r, c = heapq.heappop(heap) if r == n - 1 and c == n - 1: return t for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen: seen.add((nr, nc)) heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))复杂度
- 时间复杂度：O(n² log n)，每格入堆一次，堆操作 O(log n²)
- 空间复杂度：O(n²)，seen 标记 + 堆，最多存所有格子
可套用的代码模板
骨架：小根堆按「需要的水位」排序，代价用 max 累积，第一次弹出终点即最优。
Python
# 最小化路径最大值 · Dijkstra 变体heap = [(grid[0][0], 0, 0)] # (需要水位 t, r, c)while heap: t, r, c = heappop(heap) # 取 t 最小 if (r,c) == 终点: return t # 第一次弹出终点即答案 for 四个方向 nr, nc(未访问): push(heap, (max(t, grid[nr][nc]), nr, nc)) # max 累积易错点
面试追问把动画讲成自己的话
追问核心思路是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
火星词典
LeetCode 269 · 困难 · 沿着 高级图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题