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

约 7 分钟
文章信息 6 个分类 8 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 猿辅导
标签
数组 深度优先搜索 广度优先搜索 二分查找 矩阵 堆（优先队列） 并查集 极小化极大

题目描述

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

image-20260929104811671

image-20260929104811818

image-20260929104811967

题意分析

时间为 t 时水位也是 t，只能在上下左右相邻且高度不超过水位的格子间移动，移动本身不耗时。求从左上角到右下角的最早时间，因此需要的是一条可通行路径所要求的最低水位，而不是最少步数。

解法：最小瓶颈路径 + 最小堆

核心思路

[!blue]

固定一条路径，必须等到水位达到沿途最高格子时才能通过；达到后整条路径都可瞬间游过。因此路径代价就是经过格子的最大高度，目标是在所有路径中让这个最大值尽量小。

dist[r][c] 记录目前找到的、到达该格子所需的最小水位。起点也在路径上，所以初始化为 grid[0][0]，其他格子为无穷大。从代价为 cost 的格子走向高度为 h 的邻格，候选代价为 max(cost, h)；若比邻格已有记录小，就更新并放入最小堆。

每次弹出代价最小的状态，这个代价可以被确认。假如还存在一条更低水位的路径，沿该路径找到第一个尚未确认的格子，它的前驱已经被处理，应当早就将一个更小的候选放入堆中，与当前状态最小矛盾。关键在于延长路径只会保持或提高最大高度，不会降低代价。

一个格子更新后，堆中可能残留旧的较大记录，普通格子用 cost != dist[r][c] 跳过它们。代码在此之前检查终点也成立：若终点还有更小记录，它一定先于较大记录出堆，所以首次弹出终点时就能直接返回最优水位。只有一个格子时，起点同时是终点，也会返回起点高度。

解题步骤

  1. 将起点距离设为起点高度并入堆。
  2. 取出最小代价状态，若为终点则返回；否则跳过与最新 dist 不一致的旧记录。
  3. 对四个合法邻格计算 max(当前代价,邻格高度)。
  4. 若候选代价更小则更新并入堆，继续取堆顶。

代码实现

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;
    }
}

import "container/heap"

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
    // 标准堆已将堆顶换到末尾，接口 Pop 只负责移除末项。
    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+1))$，共有 $n^2$ 个格子，每格至多检查四条边。
  • 空间复杂度：$O(n^2)$，距离表和堆。

关键点总结

[!green]

  • 优化的是路径最大高度，不是路径长度或高度总和。
  • 起点高度本身也限制最早出发时间。
  • 该代价满足沿路径不减，适合按最小值扩展。

易错点总结

[!yellow]

  • 把转移写成 cost+h：变成另一类路径问题。
  • 直接使用普通广度优先搜索的层数作为时间：每格高度不同，步数不能代表等待水位。
  • 允许对角移动：题目只允许上下左右。
  • 将起点代价固定为零且不计起点高度：起点较高时会低估答案。

相似题目

题目 难度 关联与区别
1631. 最小体力消耗路径 中等 同样最小化路径上的最大瓶颈，原题瓶颈为相邻高度差，本题为经过格子的最高高度。
407. 接雨水 II 困难 同样用最低边界逐步抬高可达水位，本题只需到达终点，原题累计全部洼地蓄水量。
743. 网络延迟时间 中等 用优先队列取当前最优距离并松弛邻边；本题路径代价改为沿途最高水位，该题传播源点到各点的加法距离。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/43912547
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！