LeetCode 778. 水位上升的泳池中游泳

2023-04-21 HGNULB 约 15 分钟

文章信息 6 个分类 9 个标签

分类

题目描述

✅ 778. 水位上升的泳池中游泳

题意分析

给定一个 $n \times n$ 的网格，grid[i][j] 表示该位置的平台高度。时刻 $t$ 时水位为 $t$，只有当某个格子的高度不超过当前水位时，你才能待在那里。你从左上角 $(0,0)$ 出发要游到右下角 $(n-1,n-1)$，游动本身不耗时（同一时刻可以移动任意多格），只能上下左右四向移动。问最早在哪个时刻能够到达终点。

「游动不耗时」这句话是全题的题眼。它意味着路径的长度、拐了多少弯，统统无关紧要；唯一决定何时能走通的，是这条路径上最高的那块平台——只要水位涨到那个高度，整条路就同时可通行了。于是问题被精确地改写成：在所有从起点到终点的路径中，找出「路径上最大高度」的最小值。

这个目标函数值得单独强调：路径代价不是各格高度之和，而是各格高度的最大值。绝大多数最短路模板算的是求和型代价，直接套用会得出完全无关的答案。识别出「代价是取最大值」这一点，是解这道题的分水岭。

起点本身也占一格，所以答案至少是 $grid[0][0]$；同理答案也至少是 $grid[n-1][n-1]$。这两条下界不需要单独写进代码，但能帮你快速验算结果是否合理。

约束是 $1 \le n \le 50$，且 grid 恰好是 $0$ 到 $n^2-1$ 的一个排列。格子总数最多 2500，规模非常小，$O(n^2 \log n)$ 乃至 $O(n^2 \log n^2)$ 的做法都绰绰有余。「是排列」这个条件保证了高度互不相同，答案唯一且必然是某个格子的高度值——它也提示了另一条思路（二分水位 + 连通性判定），但那条路要跑多次搜索，不如一次带堆的搜索干净。

边界方面：$n = 1$ 时起点即终点，答案就是 $grid[0][0]$；网格四连通且没有障碍，所以路径必然存在，不会出现无解。

解法：Dijkstra（最小化路径最大值）

核心思路

先看两条容易想到但不够好的路。第一条是暴力枚举所有路径取最优，路径数量随 $n$ 指数增长，不可行。第二条是二分答案：猜一个水位 $T$，用广度优先搜索检查「只走高度不超过 $T$ 的格子能否从起点到终点」，因为 $T$ 越大越容易连通，可以二分。这条路是对的，复杂度 $O(n^2 \log n^2)$，但每次判定都要重跑一遍完整搜索，而且要小心 $T$ 必须不小于起点高度。

更直接的角度是把它看成一个最短路问题，只不过「路径代价」的定义换了。常规最短路里，一条路径的代价是各边权之和，松弛式是 $dist[v] = dist[u] + w$；本题的代价是各点权的最大值，松弛式相应变成

$dist[v] = \max(dist[u],\ grid[v])$

这类代价函数被称为瓶颈路（bottleneck path）。Dijkstra 的正确性只依赖代价函数的单调性——即扩展一步之后代价不会变小。求和型满足（边权非负），取最大值型同样满足（$\max(a, w) \ge a$）。所以 Dijkstra 的贪心论证原封不动地成立：每次从优先队列里取出的、代价最小的那个未定格子，它的代价已经是最终答案，不可能再被更新得更小。

显式写下状态定义：$dist[r][c]$ 表示从起点走到格子 $(r,c)$ 的所有路径中，「路径最大高度」的最小可能值。 初始时 $dist[0][0] = grid[0][0]$（起点自身的高度必须被淹没才能站上去），其余全部为正无穷表示尚未可达。

算法流程就是标准的堆优化 Dijkstra：小根堆按代价排序，反复取出代价最小的格子，向四个方向做松弛。有三处细节值得单独说明。

第一，终点判定放在出堆时而不是入堆时。 因为 Dijkstra 的保证是「出堆时代价已确定」，入堆时的值可能还会被更小的路径刷新。第一次把终点从堆里取出来的那一刻，它的代价就是答案，可以立即返回。

第二，用「懒删除」处理堆中的陈旧记录。 一个格子可能被多次入堆（每次找到更优路径就再压一次），旧记录仍留在堆里。出堆时比较 $cost$ 与 $dist[r][c]$，不相等说明这条记录已经过期，直接跳过。这比实现一个支持 decrease-key 的堆简单得多，代价只是堆里最多存 $O(n^2)$ 条记录。

第三，松弛时新代价取 $\max(cost,\ grid[nr][nc])$ 而不是 $\max(grid[r][c],\ grid[nr][nc])$。 $cost$ 是整条已走路径的最大高度，它已经把沿途所有格子的信息聚合进去了；只比较相邻两格会丢掉路径上更早出现的高峰，得出偏小的错误答案。

循环维持的不变量是：已出堆且未被跳过的格子，其 $dist$ 值就是最终答案；堆中所有记录的代价都不小于最近一次出堆的代价。 这正是 Dijkstra 的标准不变量，只是把「加法」换成了「取最大值」。

解题步骤

第一步，建立 $dist$ 数组并全部置为正无穷，然后令 $dist[0][0] = grid[0][0]$。 为什么起点的初值不是 0：你必须先站到起点这块平台上，所以水位至少要淹过 $grid[0][0]$。写成 0 会让答案在起点高度较大时偏小。

第二步，建立按代价升序的小根堆，把起点连同它的代价压入。 为什么必须是小根堆：Dijkstra 依赖「每次取出当前代价最小的未确定节点」这一贪心，用大根堆或普通队列都会破坏正确性。

第三步，循环取出堆顶。若它是终点，立即返回它的代价。 为什么可以立即返回：出堆意味着代价已确定，不存在更小的到达方式；继续搜索只是浪费。

第四步，若取出的代价与 $dist[r][c]$ 不相等，跳过这条记录。 为什么会出现不相等：同一个格子可能因为多次被松弛而多次入堆，先入堆的旧记录代价更大，出堆时早已被更优值覆盖。不跳过的话会以过期状态继续扩展，虽然结果通常仍对（因为松弛条件会挡住），但白白浪费大量堆操作。

第五步，向四个方向枚举邻居，越界的跳过。 为什么是四向：题目明确只能上下左右移动，加入对角线会得出偏小的错误答案。

第六步，计算新代价 $newCost = \max(cost,\ grid[nr][nc])$。 为什么用 $cost$ 而不是 $grid[r][c]$：$cost$ 代表整条路径迄今为止的最大高度，是需要被继承的聚合量；只看当前格会丢失路径上更早的高峰。

第七步，若 $newCost < dist[nr][nc]$，更新 $dist$ 并把新记录压入堆。 为什么用严格小于：等于时说明已有同样优的路径，再压一次只会增加堆中的冗余记录，不会改进答案。

第八步，循环结束仍未到达终点时返回 $-1$。 为什么实践中不会走到这里：网格四连通且无障碍，终点必然可达。保留这一行只是让函数在逻辑上完整。

以 grid = [[0, 2], [1, 3]] 走一遍（$n = 2$）。四个格子的高度是 $(0,0)$ 处 0、$(0,1)$ 处 2、$(1,0)$ 处 1、$(1,1)$ 处 3。

初始化：$dist$ 全为正无穷，$dist[0][0] = 0$，堆中有一条记录 $(0,\ 0,0)$。

第 1 次出堆：取出 $(0,\ 0,0)$。不是终点。$cost = 0$ 与 $dist[0][0] = 0$ 相等，记录有效。向四方向扩展：右邻 $(0,1)$ 高度 2，$newCost = \max(0, 2) = 2 < \infty$，更新 $dist[0][1] = 2$ 并入堆；下邻 $(1,0)$ 高度 1，$newCost = \max(0, 1) = 1 < \infty$，更新 $dist[1][0] = 1$ 并入堆；上邻和左邻越界跳过。堆中现有 $(1,\ 1,0)$ 和 $(2,\ 0,1)$。

第 2 次出堆：小根堆先给出代价更小的 $(1,\ 1,0)$。不是终点（终点是 $(1,1)$）。$cost = 1$ 与 $dist[1][0] = 1$ 相等，有效。扩展：右邻 $(1,1)$ 高度 3，$newCost = \max(1, 3) = 3 < \infty$，更新 $dist[1][1] = 3$ 并入堆；上邻 $(0,0)$ 的 $newCost = \max(1, 0) = 1$，但 $1 < dist[0][0] = 0$ 不成立，不更新——这正是松弛条件挡住回头路的地方。堆中现有 $(2,\ 0,1)$ 和 $(3,\ 1,1)$。

第 3 次出堆：取出 $(2,\ 0,1)$。不是终点。$cost = 2$ 与 $dist[0][1] = 2$ 相等，有效。扩展：下邻 $(1,1)$ 的 $newCost = \max(2, 3) = 3$，而 $dist[1][1]$ 已是 3，$3 < 3$ 不成立，不更新——说明从上方绕过来并不比从左边走更优，两条路的瓶颈都是那块高度 3 的终点平台。左邻 $(0,0)$ 同样被挡住。堆中只剩 $(3,\ 1,1)$。

第 4 次出堆：取出 $(3,\ 1,1)$，正是终点，立即返回 3。

答案 3 的含义是：水位涨到 3 时，路径 $(0,0) \to (1,0) \to (1,1)$ 上的三块平台高度分别是 0、1、3，全部被淹没，可以一口气游到终点；而水位为 2 时终点那块高度 3 的平台还露在水面上，无论如何都到不了。这个例子也顺带说明了为什么答案至少是 $grid[n-1][n-1]$。

顺带看一下第 3 轮体现的关键点：如果松弛时误写成 $\max(grid[r][c],\ grid[nr][nc])$，从 $(0,1)$ 扩展到 $(1,1)$ 会算出 $\max(2, 3) = 3$，本例碰巧相同；但把网格换成起点附近有一座高峰的情形（例如路径开头必须经过一块高度 9 的平台），只比较相邻两格就会把 9 丢掉，最终返回一个远小于真实值的答案。

代码实现

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        dist[0][0] = grid[0][0];
        pq.offer(new int[] {dist[0][0], 0, 0});

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0];
            int r = cur[1];
            int c = cur[2];
            if (r == n - 1 && c == n - 1) {
                return cost;
            }
            if (cost != dist[r][c]) {
                continue;
            }

            for (int[] d : dirs) {
                int nr = r + d[0];
                int nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                    continue;
                }
                int newCost = Math.max(cost, grid[nr][nc]);
                if (newCost < dist[nr][nc]) {
                    dist[nr][nc] = newCost;
                    pq.offer(new int[] {newCost, nr, nc});
                }
            }
        }

        return -1;
    }
}

type node778 struct {
    cost int
    r    int
    c    int
}

type minHeap778 []node778

func (h minHeap778) Len() int { return len(h) }
func (h minHeap778) Less(i, j int) bool { return h[i].cost < h[j].cost }
func (h minHeap778) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap778) Push(x any) { *h = append(*h, x.(node778)) }
func (h *minHeap778) Pop() any {
    old := *h
    v := old[len(old)-1]
    *h = old[:len(old)-1]
    return v
}

func swimInWater(grid [][]int) int {
    n := len(grid)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = 1 << 30
        }
    }

    dist[0][0] = grid[0][0]
    h := &minHeap778{}
    heap.Init(h)
    heap.Push(h, node778{cost: dist[0][0], r: 0, c: 0})

    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    for h.Len() > 0 {
        cur := heap.Pop(h).(node778)
        cost, r, c := cur.cost, cur.r, cur.c
        if r == n-1 && c == n-1 {
            return cost
        }
        if cost != dist[r][c] {
            continue
        }
        for _, d := range dirs {
            nr, nc := r+d[0], c+d[1]
            if nr < 0 || nr >= n || nc < 0 || nc >= n {
                continue
            }
            newCost := cost
            if grid[nr][nc] > newCost {
                newCost = grid[nr][nc]
            }
            if newCost < dist[nr][nc] {
                dist[nr][nc] = newCost
                heap.Push(h, node778{cost: newCost, r: nr, c: nc})
            }
        }
    }

    return -1
}

复杂度分析

时间复杂度：$O(n^2 \log n)$。格子数是 $n^2$，每个格子最多向四个方向松弛，所以入堆次数不超过 $4n^2$；每次堆操作是 $O(\log n^2) = O(2 \log n)$。$n \le 50$ 时格子数 2500、堆操作约一万次，运行时间可以忽略。相比「二分水位 + 每次重跑广搜」的 $O(n^2 \log n^2)$，两者同阶，但本解法只扫一遍网格，常数更小也更不容易写错。

空间复杂度：$O(n^2)$。$dist$ 数组占 $n^2$；优先队列因为采用懒删除，最坏会同时存下 $O(n^2)$ 条记录（每个格子可能被松弛多次）。这是用空间换掉 decrease-key 实现复杂度的标准取舍。

关键点总结

代价函数换了，最短路模板未必要换。Dijkstra 的正确性只要求「扩展一步后代价不减」，求和是这样，取最大值同样是这样。把松弛式从 $dist[u] + w$ 改成 $\max(dist[u], w)$，就得到了瓶颈路算法。看到「最小化路径上的最大值 / 最大化路径上的最小值」，直接套这个变体。

松弛时要继承整条路径的聚合量，而不是只看相邻两格。$cost$ 是路径迄今的最大高度，$\max(cost,\ grid[nr][nc])$ 才是新路径的瓶颈。这一点在求和型最短路里不容易搞错（因为没人会只加最后一条边），但在取最值型里是高发错误。

终点判定必须放在出堆时。Dijkstra 的保证是「出堆即确定」，入堆时的值仍可能被刷新。这条纪律在所有堆优化最短路里通用，包括求次短路、带状态最短路等变体。

懒删除是堆优化 Dijkstra 的标准工程做法。不实现 decrease-key，而是允许同一节点多次入堆，出堆时用 cost != dist 判断记录是否过期。代价是堆变大，收益是实现简单且不依赖特殊数据结构。

「不耗时移动」意味着路径长度无关紧要。题面里这类看似随口的设定，往往是在把某个维度从代价函数里彻底删掉。读题时要专门找一找「什么东西不计入代价」，那通常就是解法的入口。

面试视角：这题最想听的是「为什么这是最短路而不是动态规划」——因为可以四向移动、存在环，没有拓扑序，DP 无从下手。第二个高频追问是「Dijkstra 用在这里为什么正确」，要答出单调性：$\max(a, w) \ge a$，与边权非负是同一个条件。第三个是「还有别的解法吗」，标准答案是并查集：把所有格子按高度从小到大逐个「激活」，每激活一个就与已激活的邻居合并，当起点与终点连通时，最后激活的那个高度就是答案，复杂度 $O(n^2 \alpha(n^2))$，比堆更快；再或者二分水位加连通性判定。能主动比较这三种解法的适用场景，是这题的满分回答。

易错点总结

错误写法：松弛时写成 newCost = Math.max(grid[r][c], grid[nr][nc])。以路径必须先翻过一座高峰的网格为例（比如 $grid[0][1] = 9$ 而后续格子都很矮），从高峰走下来之后 $cost$ 应当保持 9，但只比较相邻两格会把它降回矮格的高度，最终返回一个远小于真实值的答案。$cost$ 必须沿路径继承。

错误写法：$dist[0][0]$ 初始化为 0。以 grid = [[3, 2], [0, 1]] 为例，正确答案是 3（起点自身高度就是 3，水位不到 3 连出发都做不到），初始化为 0 时算法沿 $(0,0) \to (1,0) \to (1,1)$ 累出的瓶颈只有 1，返回 1。起点也是一块必须被淹没的平台。

错误写法：把终点判定写在入堆时。以任意网格为例，终点第一次被松弛时的代价未必是最优的——后续可能通过另一条路以更小的瓶颈到达。入堆即返回会给出偏大的答案，而 Dijkstra 只保证出堆时最优。

错误写法：用普通队列（广度优先搜索）代替小根堆。以 grid = [[0, 2], [1, 3]] 为例，广搜按层扩展，不保证先处理代价最小的格子，dist 会被反复刷新且出堆顺序无意义，终点第一次被取出时的值不是最优。取最值型代价同样需要优先队列。

错误写法：松弛条件写成 newCost <= dist[nr][nc]。以任意存在多条等代价路径的网格为例，等号会让同一个格子被反复入堆，堆规模膨胀甚至在稠密等值情形下退化；答案虽仍正确，但可能因为堆操作次数暴涨而超时。

错误写法：省略 cost != dist[r][c] 的过期判断，同时又不做访问标记。以 $n = 50$ 的网格为例，每个格子会以多个陈旧代价重复出堆并重复扩展，堆操作数量成倍增加；虽然松弛条件仍能挡住错误更新，但白白浪费大量时间，属于「结果对但实现劣」。

错误写法：用一个 visited 布尔数组在入堆时打标记。以 grid = [[0, 1, 9], [9, 2, 9], [9, 3, 4]] 这类需要后续找到更优路径的网格为例，格子在第一次被松弛时就被标记为已访问，之后更优的路径无法再更新它，答案偏大。标记只能在出堆时打，或者干脆用 cost != dist 的懒删除代替。

错误写法：方向数组里加入四个对角线方向。以 grid = [[0, 9], [9, 1]] 为例，允许斜走会算出答案 1，而四向移动的正确答案是 9。题目明确限定上下左右。

错误写法：Java 的比较器写成 (a, b) -> b[0] - a[0]（大根堆）。以任意网格为例，每次取出的是代价最大的格子，Dijkstra 的贪心前提被彻底破坏，返回值基本等同于随机。方向写反是优先队列最常见的笔误。

错误写法：Go 里 Pop 从切片头部弹出（v := old[0]; *h = old[1:]）。以任意网格为例，container/heap 约定 Pop 必须弹出末尾元素（堆结构在调用前已把最小值换到末尾），从头部弹会返回错误的元素并破坏堆的内部结构，结果不可预测。

错误写法：dist 用 Integer.MAX_VALUE 初始化后又参与加法。本题的松弛是取最大值不涉及加法，所以安全；但若照搬求和型模板写成 dist[u] + w，无穷大加正数会溢出成负数，反而被判为更优，路径彻底错乱。迁移模板时要检查每一处运算。

错误写法：认为答案就是路径上所有格子高度的最小可能和。以 grid = [[0, 2], [1, 3]] 为例，最小和路径是 $0 + 1 + 3 = 4$，与答案 3 毫无关系。代价函数是取最大值，不是求和。

相似题目

题目	难度	考察点
1631. 最小体力消耗路径	中等	瓶颈是相邻格高度差的最大值而非格子高度，松弛式换成 $\max(cost, \lvert a-b \rvert)$
743. 网络延迟时间	中等	标准求和型 Dijkstra，答案取所有节点距离的最大值，可用来对照两种代价函数
787. K 站中转内最便宜的航班	中等	多了「中转次数」这一维状态，纯 Dijkstra 会失效，需按层松弛或状态扩维
505. 迷宫 II	中等	小球滚到撞墙才停，边不是相邻格而是整段滑行，建图方式与本题不同
499. 迷宫 III	困难	在最短距离基础上还要求路径字典序最小，比较器需要双关键字
1334. 阈值距离内邻居最少的城市	中等	全源最短路，点数小可直接 Floyd，训练的是「多源」与「单源」的选型
1293. 网格中的最短路径	困难	边权全为 1 但状态含「剩余消除次数」，用带状态的广搜而非优先队列
305. 岛屿数量 II	困难	逐个激活格子并合并邻居，正是本题并查集解法的核心操作
1091. 二进制矩阵中的最短路径	中等	八向移动、边权为 1 的纯广搜，可用来对照「何时不需要优先队列」