题目描述
思路解析动画文字版
这就是 Dijkstra 的味道：把「路径代价 = 路上最大高度」当作距离，贪心地永远先扩展代价最小的格。
起点 (0,0) 高度 0 放进堆。堆里永远是「下一步能踏上的边界格」，按高度排，最浅的排最前。
弹出当前堆里最浅的格 (0,0) 高度 0（橘色）。它已确定到达，ans 更新为 max 前值与 0 = 0。接着把它四周还没确定的邻居放进堆。
邻居 (1,0) 高度 1 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
邻居 (0,1) 高度 2 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
弹出当前堆里最浅的格 (1,0) 高度 1（橘色）。它已确定到达，ans 更新为 max 前值与 1 = 1。接着把它四周还没确定的邻居放进堆。
邻居 (2,0) 高度 8 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
邻居 (1,1) 高度 3 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
弹出当前堆里最浅的格 (0,1) 高度 2（橘色）。它已确定到达，ans 更新为 max 前值与 2 = 2。接着把它四周还没确定的邻居放进堆。
邻居 (0,2) 高度 5 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
弹出当前堆里最浅的格 (1,1) 高度 3（橘色）。它已确定到达，ans 更新为 max 前值与 3 = 3。接着把它四周还没确定的邻居放进堆。
邻居 (2,1) 高度 6 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
邻居 (1,2) 高度 4 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
弹出当前堆里最浅的格 (1,2) 高度 4（橘色）。它已确定到达，ans 更新为 max 前值与 4 = 4。接着把它四周还没确定的邻居放进堆。
邻居 (2,2) 高度 7 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
弹出当前堆里最浅的格 (0,2) 高度 5（橘色）。它已确定到达，ans 更新为 max 前值与 5 = 5。接着把它四周还没确定的邻居放进堆。
弹出当前堆里最浅的格 (2,1) 高度 6（橘色）。它已确定到达，ans 更新为 max 前值与 6 = 6。接着把它四周还没确定的邻居放进堆。
弹出终点 (2,2) 高度 7！一路最大高度 ans = 7，这就是答案：第一次摸到右下角时的 ans 一定最优。
到达右下角，最早时刻 = 7。蓝灰是探索过的格。现在沿父指针回溯，把真正走的那条路逐格点亮。
路径点亮 (0,0) 高度 0（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
路径点亮 (1,0) 高度 1（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
路径点亮 (1,1) 高度 3（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
路径点亮 (1,2) 高度 4（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
路径点亮 (2,2) 高度 7（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
边界先想清。
两个高频追问。
参考代码
import heapqdef swimInWater(grid): n = len(grid) seen = {(0, 0)} pq = [(grid[0][0], 0, 0)] # (高度, i, j) ans = 0 while pq: h, i, j = heapq.heappop(pq) ans = max(ans, h) if i == n - 1 and j == n - 1: return ans for di, dj in ((1,0),(-1,0),(0,1),(0,-1)): ni, nj = i + di, j + dj if 0 <= ni < n and 0 <= nj < n \ and (ni, nj) not in seen: seen.add((ni, nj)) heapq.heappush(pq, (grid[ni][nj], ni, nj)) return ans复杂度
- 时间：O(N²·logN)，每格进堆一次，堆操作 logN（N² 个格）
- 空间：O(N²)，堆 + 访问标记矩阵
易错点
面试追问把动画讲成自己的话
追问为什么第一次弹出终点时 ans 就是最优，不用再找？
追问除了优先队列还有别的解法吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
火星词典
LeetCode 269 · 困难 · 沿着 高级图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题