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

约 8 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 阿里 图森
标签
数组 深度优先搜索 广度优先搜索 矩阵

题目描述

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

image-20260928224111852

image-20260928224111854

image-20260928224111856

题意分析

水只能流向上下左右相邻且高度不超过当前格子的地方。太平洋连接上边界和左边界，大西洋连接下边界和右边界，需要找出分别存在路径流到两片海洋的格子。

直接从每个格子向下游搜索两片海洋，会重复访问大量路径。可以反过来从海岸出发，寻找哪些格子的水能够流到这片海洋。

解法：边界反向 BFS

核心思路

[!blue]

若水能从邻格 next 流到当前格 cur，必须满足 height[next] >= height[cur]。把这条边反向，就能从 cur 走向不低于它的 next。所以原来的不升高路径，与反向搜索中的不降低路径一一对应。

对太平洋，把所有上边界和左边界格子作为起点，进行一次多源 BFS。它们本来就能直接流入太平洋；反向扩展到的每个新格子都能先流回已有格子，再沿已知路径到达海洋。沿任意真实水流路径反向走，也一定能从海岸找到它，因此不会漏掉可达位置。

大西洋同理，从下边界和右边界独立搜索。使用 pacific、atlantic 两套访问标记，最后只保留同时被两次搜索访问的格子。两条流向海洋的路径可以不同，只要分别存在即可。

等高格子也允许互相流动，反向搜索必须保留等号，同时在入队时立刻标记，避免等高环路和多个来源让同一格反复入队。海岸交点、单行或单列矩阵中的重复起点，也由同一套去重逻辑处理。

解题步骤

  1. 建立两套访问表和队列。将上、左边界加入太平洋队列，下、右边界加入大西洋队列，每次加入前检查并设置对应访问标记。
  2. 分别执行两次 BFS。每次取出一个格子，枚举四个邻居。
  3. 跳过越界、已访问或高度低于当前格的邻居；其余邻居立即标记并入队。
  4. 队列为空时，该海洋的全部可达来源已经找到。
  5. 扫描整个矩阵，将两套标记都为真的坐标加入结果。

代码实现

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(mn)$，每片海至多访问每格一次。
  • 空间复杂度：$O(mn)$，两套标记与队列。

关键点总结

[!green]

  • 反向搜索将“每个格子能否到海”转成“从海岸能逆向到哪些格子”，每片海只搜索一次。
  • 正向不升高对应反向不降低，移动方向改变时高度不等式也必须反转。
  • 两片海的可达集合独立计算，交集才是最终答案。
  • 发现时标记保证每格在每次搜索中最多入队一次。

易错点总结

[!yellow]

  • 从海岸出发后仍沿下坡搜索，会把水流方向用反。
  • 不能排除等高邻居，平地上的水同样可以流动；也不能因此省掉访问标记。
  • 每片海都对应两条边界，只加入其中一条会漏掉其他直接入海的起点。
  • 两片海不能共用一个访问表，否则第一次搜索的访问状态会阻止第二次搜索，也无法判断交集。

相似题目

题目 难度 关联与区别
130. 被围绕的区域 中等 同样从边界反向寻找可连通区域，本题从两片海洋分别搜索并取交集。
329. 矩阵中的最长递增路径 困难 同样按高度限制移动，本题反向允许走到不低的格子，相等高度可能成环，必须标记访问。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/28103603
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！