LeetCode 778困难高级图
在水位上升的泳池中游泳 图解题解
这道题到底在问什么
水位随时间升高，求从左上游到右下所需最早时间。
- grid
- [[0,1,9],[8,1,9],[8,1,1]]
- 输出
- 1（绕开 8、9，全程水位 ≤1）
最优解：一步一步想明白
- 3按普通最短步数走会忽略高度瓶颈。
- 4把路径代价定义为一路上的最大高度，用小根堆每次扩展当前最小瓶颈路径。
- 5t = 从起点到某格、路径上的最高水位。用小根堆每次弹出 t 最小的格子扩展(Dijkstra 变体)。起点 (0,0) t=0。灰格是 8、9 的高墙。
- 6起点四周入堆：(0,1) 需 t=max(0,1)=1，(1,0) 需 t=max(0,8)=8。堆顶 t=1 最小 → 确认 (0,1)。
- 7从 (0,1) 扩展：(1,1) 需 t=max(1,1)=1；(0,2)=9 这种高墙 t 巨大、沉到堆底。继续弹 t=1 → 确认 (1,1)。
- 8继续沿 t=1 的格子走，确认 (2,1)。
- 9关键帧：第一次从堆里弹出终点 (2,2)，此时 t=1 → 答案 1。Dijkstra 保证：第一次弹出终点的 t，就是所有路径里「最高水位的最小值」。全程绕开了 8、9 的高地。
- 12一句话记住：把路径代价定义为一路上的最大高度，用小根堆每次扩展当前最小瓶颈路径。
- 21这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：按普通最短「步数」BFS
✓ 对：代价是路径上的最高水位，用 max 累积
本题要最小化路径最大高度，不是步数；普通 BFS 求不出。
✗ 错：用普通队列扩展
✓ 对：用小根堆(按 t 排序)，即 Dijkstra
每次要先扩展当前 t 最小的格子，普通队列做不到。
✗ 错：代价用加法累积
✓ 对：t = max(t, grid[next])
路径代价是沿途最高水位(取 max)，不是高度之和。
完整代码（Python / C++ / Java）
Python
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))C++
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> seen(n, vector<int>(n));
using T = tuple<int,int,int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({grid[0][0],0,0});
seen[0][0] = 1;
int d[5] = {1,0,-1,0,1};
while (!pq.empty()) {
auto [t,r,c] = pq.top(); pq.pop();
if (r == n-1 && c == n-1) return t;
for (int k=0;k<4;k++) {
int nr=r+d[k], nc=c+d[k+1];
if (nr>=0&&nr<n&&nc>=0&&nc<n&&!seen[nr][nc]) {
seen[nr][nc]=1;
pq.push({max(t, grid[nr][nc]), nr, nc});
}
}
}
return 0;
}
};Java
class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
boolean[][] seen = new boolean[n][n];
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{grid[0][0],0,0});
seen[0][0] = true;
int[] d = {1,0,-1,0,1};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[1] == n-1 && cur[2] == n-1) return cur[0];
for (int k=0;k<4;k++) {
int nr=cur[1]+d[k], nc=cur[2]+d[k+1];
if (nr>=0&&nr<n&&nc>=0&&nc<n&&!seen[nr][nc]) {
seen[nr][nc]=true;
pq.offer(new int[]{Math.max(cur[0], grid[nr][nc]), nr, nc});
}
}
}
return 0;
}
}套路模板 · Dijkstra(max 代价)
# 最小化路径最大值 · 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 累积复杂度
时间复杂度
O(n² log n)
每格入堆一次，堆操作 O(log n²)
空间复杂度
O(n²)
seen 标记 + 堆，最多存所有格子
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 在水位上升的泳池中游泳 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
把路径代价定义为一路上的最大高度，用小根堆每次扩展当前 t 最小的格子(Dijkstra 变体)；第一次弹出终点时的 t 就是答案。
这道题为什么用「高级图」，换最直接的暴力解会差在哪？+
高级图抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。