LeetCode 417. 太平洋大西洋水流问题

2025-05-17 HGNULB 约 11 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 417. 太平洋大西洋水流问题

题意分析

给一个高度矩阵，左边界和上边界之外是太平洋，右边界和下边界之外是大西洋。雨水从任意格子出发，只能流向高度不高于自己的四邻格子。要找出所有既能流到太平洋、又能流到大西洋的格子坐标。

「不高于」这三个字要抠清楚：允许平流，也就是等高的相邻格子之间可以互相流动。如果错写成严格递减，大片高原地带会被漏掉。

边界格子天然贴着海洋：第一行和第一列上的格子已经在太平洋岸边，最后一行和最后一列上的格子已经在大西洋岸边。四个角同时贴着两片海洋——左上角与右下角各自紧邻两洋，因此这两个角必然在答案里。

输出是坐标列表，顺序不限，但每个坐标只能出现一次。这提示实现时要有明确的去重机制。

规模上矩阵是两百乘两百量级，允许对每个格子做常数次访问，但不允许对每个格子各跑一次完整搜索。

解法：边界反向 BFS

核心思路

按题意正着做，就是对每个格子发起一次搜索，看水能不能顺流到达两片海洋。这样每个格子都要遍历一遍与它相连的下坡区域，最坏情况下总代价是格子数的平方，而且相邻格子的搜索路径大量重复。

突破口是把水流方向反过来。「水能从 A 流到海」等价于「从海出发逆流而上能走到 A」。逆流的规则也随之翻转：正向要求下一格高度不高于当前格，反向就要求下一格高度不低于当前格。

这一反转的价值在于起点合并：正向有 $m \cdot n$ 个不同的起点，反向只有两组固定起点——太平洋沿岸的一整行加一整列，大西洋沿岸的一整行加一整列。于是只需要两次多源遍历，每次把各自海洋能逆流到达的格子全部标记出来。

维持的不变量是：某个格子在太平洋标记矩阵中为真，当且仅当水能从它流入太平洋；大西洋同理。两次遍历互不干扰，各用一套访问标记。最后扫一遍矩阵，两个标记同时为真的格子就是答案，天然去重、天然按行优先有序。

遍历方式用广度优先还是深度优先都行，因为这里只关心可达性、不关心距离。选队列版是为了避免在两百乘两百的矩阵上递归过深。

解题步骤

准备两个与矩阵同形的布尔标记数组和两个队列，分别对应两片海洋。两套标记必须完全独立，共用一套就无法区分「能流到哪一片」。

把第一列和第一行的所有格子放进太平洋队列，把最后一列和最后一行的所有格子放进大西洋队列。入队时立刻打标记，并且先检查是否已标记——左上角会被行循环和列循环各碰一次，重复入队虽不影响正确性但会浪费队列空间。

对两个队列各跑一次遍历。取出一个格子后枚举四个方向，依次检查：是否越界、是否已访问、高度是否低于当前格。三个条件任一成立就跳过。

高度判断的方向是本题的核心：只有当邻居不低于当前格时才继续扩展，因为水正是从那个更高（或等高）的邻居流向当前格的。写成大于会漏掉等高平流的情况。

访问标记在入队时打，不是出队时打。边界上有大量起点，出队时才标记会让同一格子被多个方向重复推入，队列规模成倍膨胀。

两次遍历都结束后，按行优先扫描整个矩阵，收集两个标记都为真的坐标。扫描顺序天然保证了每个坐标只输出一次。

以 heights = [[1,2,3],[8,9,4],[7,6,5]] 走一遍：这是一个从左上角向内盘旋上升的矩阵。

先做太平洋方向。起点是第一行 (0,0)、(0,1)、(0,2) 和第一列 (1,0)、(2,0)，共五个格子（左上角只入队一次）。从 (0,0) 高度 1 出发，邻居 (1,0) 高度 8 和 (0,1) 高度 2 都已在起点集合中。从 (0,1) 高度 2 出发，下方 (1,1) 高度 9 不低于 2，标记入队。从 (0,2) 高度 3 出发，下方 (1,2) 高度 4 不低于 3，标记入队。从 (1,0) 高度 8 出发，下方 (2,0) 高度 7 低于 8，跳过（它本就是起点）。从 (2,0) 高度 7 出发，右方 (2,1) 高度 6 低于 7，跳过。从 (1,1) 高度 9 出发，四周的 6 和 4 都更低，无新增。从 (1,2) 高度 4 出发，下方 (2,2) 高度 5 不低于 4，标记入队。从 (2,2) 高度 5 出发，左方 (2,1) 高度 6 不低于 5，标记入队。至此九个格子全部被太平洋标记。

再做大西洋方向。起点是最后一列 (0,2)、(1,2)、(2,2) 和最后一行 (2,0)、(2,1)，共五个。从 (0,2) 高度 3 出发，左方 (0,1) 高度 2 低于 3，跳过。从 (1,2) 高度 4 出发，左方 (1,1) 高度 9 不低于 4，标记入队。从 (2,0) 高度 7 出发，上方 (1,0) 高度 8 不低于 7，标记入队。从 (2,1) 高度 6 出发，上方 (1,1) 已标记。从 (1,1) 高度 9 出发，上方 (0,1) 高度 2 和左方 (1,0) 高度 8 都更低，跳过。从 (1,0) 高度 8 出发，上方 (0,0) 高度 1 更低，跳过。大西洋最终标记了七个格子，缺 (0,0) 和 (0,1)。

两套标记求交集，按行优先扫描得到 [[0,2], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]]，共七个。验证 (0,1)：它高度为 2，向右只能到高度 3 的 (0,2)（更高，流不过去），向下只能到高度 9 的 (1,1)（更高），唯一能流的方向是向左到 (0,0) 再入太平洋，确实到不了大西洋，被正确排除。

代码实现

class Solution {
    // 反向移动时，只有相邻格子高度大于等于当前格子，才说明水可以从那个相邻格子流回当前海洋。
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;

        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        Queue<int[]> pacificQueue = new ArrayDeque<>();
        Queue<int[]> atlanticQueue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            offer(pacificQueue, pacific, i, 0);
            offer(atlanticQueue, atlantic, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            offer(pacificQueue, pacific, 0, j);
            offer(atlanticQueue, atlantic, m - 1, j);
        }

        bfs(heights, pacificQueue, pacific);
        bfs(heights, atlanticQueue, atlantic);

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    res.add(cell);
                }
            }
        }

        return res;
    }

    private void offer(Queue<int[]> queue, boolean[][] visited, int row, int col) {
        if (visited[row][col]) {
            return;
        }

        visited[row][col] = true;
        queue.offer(new int[] {row, col});
    }

    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] visited) {
        int m = heights.length;
        int n = heights[0].length;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int nextRow = cur[0] + dir[0];
                int nextCol = cur[1] + dir[1];
                if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) {
                    continue;
                }
                if (visited[nextRow][nextCol]) {
                    continue;
                }
                if (heights[nextRow][nextCol] < heights[cur[0]][cur[1]]) {
                    continue;
                }

                visited[nextRow][nextCol] = true;
                queue.offer(new int[] {nextRow, nextCol});
            }
        }
    }
}

func pacificAtlantic(heights [][]int) [][]int {
    // 反向移动时，只有相邻格子高度大于等于当前格子，才说明水可以从那个相邻格子流回当前海洋。
    m, n := len(heights), len(heights[0])
    pacific := make([][]bool, m)
    atlantic := make([][]bool, m)
    for i := 0; i < m; i++ {
        pacific[i] = make([]bool, n)
        atlantic[i] = make([]bool, n)
    }

    pacificQueue := make([][2]int, 0)
    atlanticQueue := make([][2]int, 0)
    push := func(queue *[][2]int, visited [][]bool, row, col int) {
        if visited[row][col] {
            return
        }

        visited[row][col] = true
        *queue = append(*queue, [2]int{row, col})
    }

    for i := 0; i < m; i++ {
        push(&pacificQueue, pacific, i, 0)
        push(&atlanticQueue, atlantic, i, n-1)
    }
    for j := 0; j < n; j++ {
        push(&pacificQueue, pacific, 0, j)
        push(&atlanticQueue, atlantic, m-1, j)
    }

    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    bfs := func(queue [][2]int, visited [][]bool) {
        for head := 0; head < len(queue); head++ {
            cur := queue[head]
            for _, dir := range dirs {
                nextRow := cur[0] + dir[0]
                nextCol := cur[1] + dir[1]
                if nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n {
                    continue
                }
                if visited[nextRow][nextCol] {
                    continue
                }
                if heights[nextRow][nextCol] < heights[cur[0]][cur[1]] {
                    continue
                }

                visited[nextRow][nextCol] = true
                queue = append(queue, [2]int{nextRow, nextCol})
            }
        }
    }

    bfs(pacificQueue, pacific)
    bfs(atlanticQueue, atlantic)

    res := make([][]int, 0)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pacific[i][j] && atlantic[i][j] {
                res = append(res, []int{i, j})
            }
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(m \cdot n)$，两次遍历各自让每个格子最多入队一次、出队后检查四个方向，最后的收集扫描也是一遍全表，三部分都是格子数的常数倍。

空间复杂度：$O(m \cdot n)$，两个布尔标记矩阵各占一份网格大小，队列最坏时容纳全部格子，输出列表在极端情况下同样是这个量级。

关键点总结

起点太多时反转搜索方向。「每个点能否到达目标集合」翻译成「从目标集合出发能到达哪些点」，把 $m \cdot n$ 次搜索压成常数次多源遍历，这是网格题最高频的降复杂度手法。

方向反转的同时，转移条件也必须取反。正向的「不高于」对应反向的「不低于」，这一步漏掉会得出完全相反的结果。

需要区分「属于哪一类」时就用多套独立标记，最后求交集。合用一套标记只能回答「能否到达任意一片海」，回答不了「是否两片都能到」。

等号的归属要从题意里读，不能凭直觉。本题允许等高平流，所以两个方向的判断都必须包含等号。

面试视角：先讲正向做法为什么慢，再讲反转带来的起点合并，这个推导过程本身就是考点。写完可以补一句「深度优先版本代码更短，但两百乘两百的矩阵递归深度可达四万，队列版更稳妥」，体现工程判断。

易错点总结

错误写法：反向遍历时仍用「邻居高度不高于当前格」的条件。heights = [[1,2,3],[8,9,4],[7,6,5]] → 从边界出发只能走下坡，标记结果与真实可达关系恰好相反，输出几乎全错。

错误写法：把不等号写成严格的「邻居高度大于当前格」。存在等高平原的矩阵，如 [[1,1],[1,1]] → 平流被禁止，中间格子无法被标记，正确答案应包含全部四个格子。

错误写法：两片海洋共用一个访问标记矩阵。任意用例 → 只能得出「能流到某片海」的结论，无法判断是否两片都能到，输出会包含大量不合格的坐标。

错误写法：太平洋起点只放第一行，忘了第一列（或大西洋只放最后一列，忘了最后一行）。heights = [[1,2,3],[8,9,4],[7,6,5]] → (1,0)、(2,0) 这些左边界格子拿不到太平洋标记，答案漏项。

错误写法：边界入队时不检查是否已标记。矩阵的四个角 → 会被行循环和列循环各推一次，队列里出现重复元素；若同时又把标记推迟到出队，重复会进一步放大。

错误写法：把访问标记放在出队时打。边界起点很多的矩阵 → 同一个格子被相邻的多个起点重复推入队列，队列规模成倍膨胀。

错误写法：越界检查放在读取邻居高度之后。第 0 行的任意格子向上扩展 → 先访问 heights[-1][j] 直接抛出越界异常。

错误写法：在遍历过程中就把满足条件的坐标加入结果列表。任意用例 → 一个格子可能先被太平洋标记、后被大西洋标记，收集时机不对会漏收或重复收，必须等两次遍历都结束后统一扫描。

错误写法：假设矩阵是方阵，用同一个边长校验行列下标。heights = [[1, 2, 3]] 这类单行矩阵 → 列方向的合法下标被误判越界，右侧格子拿不到标记。

错误写法：认为单行或单列矩阵需要特判。heights = [[1, 2]] → 实际上每个格子都同时贴着两片海洋，通用流程会自然把它们全部标记，额外的特判反而容易写错。

相似题目

题目	难度	考察点
130. 被围绕的区域	中等	同为从边界反向标记，标记的是「不该被翻转」的安全区
1020. 飞地的数量	中等	从边界扩散后统计未被触及的格子数量
1254. 统计封闭岛屿的数目	中等	需要在连通块遍历中判断该块是否触碰过边界
200. 岛屿数量	中等	基础的连通块计数，转移条件不含高度比较
695. 岛屿的最大面积	中等	在连通块遍历中顺带累计规模并取最大值
934. 最短的桥	中等	先用一次遍历圈出一座岛，再以整座岛为多源向外扩散