在水位上升的泳池中游泳 图解题解

这道题到底在问什么

输入

3×3 高度矩阵

输出

答案 = 7

最优解：一步一步想明白

1. 3这就是 Dijkstra 的味道：把「路径代价 = 路上最大高度」当作距离，贪心地永远先扩展代价最小的格。
2. 4起点 (0,0) 高度 0 放进堆。堆里永远是「下一步能踏上的边界格」，按高度排，最浅的排最前。
3. 5弹出当前堆里最浅的格 (0,0) 高度 0（橘色）。它已确定到达，ans 更新为 max 前值与 0 = 0。接着把它四周还没确定的邻居放进堆。
4. 6邻居 (1,0) 高度 1 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
5. 7邻居 (0,1) 高度 2 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
6. 8弹出当前堆里最浅的格 (1,0) 高度 1（橘色）。它已确定到达，ans 更新为 max 前值与 1 = 1。接着把它四周还没确定的邻居放进堆。
7. 9邻居 (2,0) 高度 8 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
8. 10邻居 (1,1) 高度 3 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
9. 11弹出当前堆里最浅的格 (0,1) 高度 2（橘色）。它已确定到达，ans 更新为 max 前值与 2 = 2。接着把它四周还没确定的邻居放进堆。
10. 12邻居 (0,2) 高度 5 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
11. 13弹出当前堆里最浅的格 (1,1) 高度 3（橘色）。它已确定到达，ans 更新为 max 前值与 3 = 3。接着把它四周还没确定的邻居放进堆。
12. 14邻居 (2,1) 高度 6 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
13. 15邻居 (1,2) 高度 4 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
14. 16弹出当前堆里最浅的格 (1,2) 高度 4（橘色）。它已确定到达，ans 更新为 max 前值与 4 = 4。接着把它四周还没确定的邻居放进堆。
15. 17邻居 (2,2) 高度 7 入堆（浅橘）。它现在是候选边界，等以后轮到它是堆里最浅的格时再扩散。
16. 18弹出当前堆里最浅的格 (0,2) 高度 5（橘色）。它已确定到达，ans 更新为 max 前值与 5 = 5。接着把它四周还没确定的邻居放进堆。
17. 19弹出当前堆里最浅的格 (2,1) 高度 6（橘色）。它已确定到达，ans 更新为 max 前值与 6 = 6。接着把它四周还没确定的邻居放进堆。
18. 20弹出终点 (2,2) 高度 7！一路最大高度 ans = 7，这就是答案：第一次摸到右下角时的 ans 一定最优。
19. 21到达右下角，最早时刻 = 7。蓝灰是探索过的格。现在沿父指针回溯，把真正走的那条路逐格点亮。
20. 22路径点亮 (0,0) 高度 0（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
21. 23路径点亮 (1,0) 高度 1（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
22. 24路径点亮 (1,1) 高度 3（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
23. 25路径点亮 (1,2) 高度 4（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。
24. 26路径点亮 (2,2) 高度 7（绿色）。整条路上最高的一格就是 7，水位涨到 7 时这条路全程可游。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import heapq
def 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

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        priority_queue<array<int,3>,
            vector<array<int,3>>, greater<>> pq;
        vector<vector<bool>> seen(n, vector<bool>(n));
        pq.push({grid[0][0], 0, 0});
        seen[0][0] = true;
        int ans = 0, d[5] = {1, 0, -1, 0, 1};
        while (!pq.empty()) {
            auto [h, i, j] = pq.top(); pq.pop();
            ans = max(ans, h);
            if (i == n - 1 && j == n - 1) return ans;
            for (int k = 0; k < 4; k++) {
                int ni = i + d[k], nj = j + d[k + 1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n
                    && !seen[ni][nj]) {
                    seen[ni][nj] = true;
                    pq.push({grid[ni][nj], ni, nj});
                }
            }
        }
        return ans;
    }
};

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]);   // 按高度小顶堆
        boolean[][] seen = new boolean[n][n];
        pq.offer(new int[]{grid[0][0], 0, 0});
        seen[0][0] = true;
        int ans = 0;
        int[] d = {1, 0, -1, 0, 1};
        while (!pq.isEmpty()) {
            int[] c = pq.poll();
            int h = c[0], i = c[1], j = c[2];
            ans = Math.max(ans, h);
            if (i == n - 1 && j == n - 1) return ans;
            for (int k = 0; k < 4; k++) {
                int ni = i + d[k], nj = j + d[k + 1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n
                    && !seen[ni][nj]) {
                    seen[ni][nj] = true;
                    pq.offer(new int[]{grid[ni][nj], ni, nj});
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问