LeetCode 417. 太平洋大西洋水流问题
字数 2785 2025-10-26 09:00:52

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

题目描述

有一个 m x n 的矩形岛屿，其左上角与“太平洋”接壤，右下角与“大西洋”接壤。岛屿被分成多个正方形单元格，给定一个 m x n 的整数矩阵 heights，其中 heights[r][c] 表示坐标 (r, c) 处单元格的高度。

雨水只能从高处流向低处或等高的相邻单元格（相邻单元格指上、下、左、右四个方向）。请找出所有既能流向太平洋，也能流向大西洋的单元格的坐标，并以任意顺序返回这些坐标的列表。

解题过程

这个问题的核心是“反向思考”。如果从每个单元格出发，尝试寻找一条路径流向两个海洋，计算量会非常大（因为每个单元格都要尝试所有可能的路径）。一个更巧妙的思路是：从海洋的边界开始，“逆流而上”（即从低处流向高处，或者说水可以流过来的反方向），标记所有能够到达的单元格。这样，我们只需要从边界出发进行两次搜索（一次从太平洋边界，一次从大西洋边界），最后找出那些同时被两次搜索标记过的单元格即可。

步骤一：问题分析与思路确立

  1. 目标：找到所有能同时流向太平洋和大西洋的单元格 (r, c)。
  2. 关键观察：水流方向是从高到低（或等高）。反过来，如果水能从某个单元格 A 流到海洋，那么从海洋边界出发，沿着相反的方向（即从低到高，或等高），我们就能“反向”到达单元格 A。
  3. 核心思路：使用深度优先搜索（DFS）或广度优先搜索（BFS）进行“反向”遍历。
    • 从所有与太平洋接壤的边界单元格（第一行和第一列）出发，进行DFS/BFS，标记所有能够“逆流”到达的单元格（即水能从这里流到太平洋的单元格）。我们将其记录在一个集合或一个标记矩阵中，比如 pacific_reachable。
    • 从所有与大西洋接壤的边界单元格（最后一行和最后一列）出发，进行同样的DFS/BFS，标记所有能够“逆流”到达的单元格（即水能从这里流到大西洋的单元格）。记录在 atlantic_reachable 中。
    • 最终结果就是那些既出现在 pacific_reachable 中，又出现在 atlantic_reachable 中的单元格。

步骤二：定义DFS函数

我们将定义一个DFS递归函数，它负责从一个给定的单元格开始，向四个方向“逆流”探索。

  1. 函数签名： dfs(row, col, reachable, prev_height)

    • row, col: 当前正在访问的单元格坐标。
    • reachable: 一个标记矩阵（大小也是 m x n），用于记录哪些单元格可以被某个海洋“反向”到达。reachable[r][c] 为 True 表示该单元格可到达。
    • prev_height: 上一个单元格（即水流来源的海洋或已探索的单元格）的高度。这个参数至关重要，用于判断是否可以“逆流”到当前单元格。

  2. DFS函数的执行步骤（递归过程）：
    a. 边界检查：首先检查当前 (row, col) 是否在矩阵范围内。如果越界，直接返回。
    b. 可达性检查：检查当前单元格是否已经被标记过 (reachable[row][col] 为 True)。如果已经标记过，说明已经探索过，直接返回以避免重复计算和无限递归。
    c. 高度检查（“逆流”条件）：这是最关键的一步。我们要模拟水从海洋流过来。prev_height 是“上游”的高度。当前单元格 heights[row][col] 是“下游”的高度。水只能从高往低流，所以“反向”探索时，我们必须保证“下游”的高度（当前单元格）不低于 “上游”的高度（prev_height），即 heights[row][col] >= prev_height。如果当前单元格的高度小于 prev_height，说明水无法从当前这个低洼处流回到那个高的“上游”点，因此这个方向探索终止，直接返回。
    d. 标记当前单元格：如果通过了以上所有检查，说明当前单元格可以被“反向”到达。将其在 reachable 矩阵中标记为 True。
    e. 递归探索邻居：以当前单元格的高度 heights[row][col] 作为新的 prev_height，递归地调用DFS函数，探索其上、下、左、右四个方向的邻居单元格。

步骤三：主算法流程

现在我们将DFS函数应用到整个问题上。

  1. 初始化：

    • 获取矩阵的行数 m 和列数 n。
    • 创建两个大小均为 m x n 的布尔矩阵 pacific_reachable 和 atlantic_reachable，初始值全部为 False。

  2. 从太平洋边界开始DFS：

    • 太平洋边界是第一行（row = 0）和第一列（col = 0）的所有单元格。
    • 对于第一行的每一个单元格 (0, col)，调用 dfs(0, col, pacific_reachable, heights[0][col])。注意，这里的 prev_height 初始值就是边界单元格自身的高度。因为海洋是起点，我们认为水从海洋（高度为边界单元格高度）流过来。
    • 对于第一列的每一个单元格 (row, 0)，调用 dfs(row, 0, pacific_reachable, heights[row][0])。

  3. 从大西洋边界开始DFS：

    • 大西洋边界是最后一行（row = m-1）和最后一列（col = n-1）的所有单元格。
    • 对于最后一行的每一个单元格 (m-1, col)，调用 dfs(m-1, col, atlantic_reachable, heights[m-1][col])。
    • 对于最后一列的每一个单元格 (row, n-1)，调用 dfs(row, n-1, atlantic_reachable, heights[row][n-1])。

  4. 收集结果：

    • 创建一个空列表 result 用于存放结果坐标。
    • 遍历整个矩阵的每一个单元格 (i, j)。
    • 如果 pacific_reachable[i][j] 和 atlantic_reachable[i][j] 都为 True，说明这个单元格的水既能流到太平洋，也能流到大西洋。
    • 将这个单元格的坐标 (i, j) 添加到 result 列表中。
    • 最终返回 result 列表。

总结

这个算法通过“反向思考”，将问题从“每个点能否流到海”转化为“海的水能逆流到哪些点”，极大地降低了计算复杂度。我们通过两次DFS/BFS（一次针对太平洋，一次针对大西洋）来标记可达区域，最后求交集。这种方法的时间复杂度和空间复杂度都是 O(m * n)，其中 m 和 n 是矩阵的尺寸。

LeetCode 417. 太平洋大西洋水流问题 题目描述 有一个 m x n 的矩形岛屿，其左上角与“太平洋”接壤，右下角与“大西洋”接壤。岛屿被分成多个正方形单元格，给定一个 m x n 的整数矩阵 heights ，其中 heights[r][c] 表示坐标 (r, c) 处单元格的高度。 雨水只能从高处流向低处或等高的相邻单元格（相邻单元格指上、下、左、右四个方向）。请找出所有既能流向太平洋，也能流向大西洋的单元格的坐标，并以任意顺序返回这些坐标的列表。 解题过程 这个问题的核心是“反向思考”。如果从每个单元格出发，尝试寻找一条路径流向两个海洋，计算量会非常大（因为每个单元格都要尝试所有可能的路径）。一个更巧妙的思路是：从海洋的边界开始，“逆流而上”（即从低处流向高处，或者说水可以流过来的反方向），标记所有能够到达的单元格。这样，我们只需要从边界出发进行两次搜索（一次从太平洋边界，一次从大西洋边界），最后找出那些同时被两次搜索标记过的单元格即可。 步骤一：问题分析与思路确立 目标 ：找到所有能同时流向太平洋和大西洋的单元格 (r, c)。 关键观察 ：水流方向是从高到低（或等高）。反过来，如果水能从某个单元格 A 流到海洋，那么从海洋边界出发，沿着相反的方向（即从低到高，或等高），我们就能“反向”到达单元格 A。 核心思路 ：使用深度优先搜索（DFS）或广度优先搜索（BFS）进行“反向”遍历。 从所有与 太平洋 接壤的边界单元格（第一行和第一列）出发，进行DFS/BFS，标记所有能够“逆流”到达的单元格（即水能从这里流到太平洋的单元格）。我们将其记录在一个集合或一个标记矩阵中，比如 pacific_reachable 。 从所有与 大西洋 接壤的边界单元格（最后一行和最后一列）出发，进行同样的DFS/BFS，标记所有能够“逆流”到达的单元格（即水能从这里流到大西洋的单元格）。记录在 atlantic_reachable 中。 最终结果就是那些既出现在 pacific_reachable 中，又出现在 atlantic_reachable 中的单元格。 步骤二：定义DFS函数 我们将定义一个DFS递归函数，它负责从一个给定的单元格开始，向四个方向“逆流”探索。 函数签名 ： dfs(row, col, reachable, prev_height) row, col : 当前正在访问的单元格坐标。 reachable : 一个标记矩阵（大小也是 m x n），用于记录哪些单元格可以被某个海洋“反向”到达。 reachable[r][c] 为 True 表示该单元格可到达。 prev_height : 上一个 单元格（即水流来源的海洋或已探索的单元格）的高度。这个参数至关重要，用于判断是否可以“逆流”到当前单元格。 DFS函数的执行步骤（递归过程） ： a. 边界检查 ：首先检查当前 (row, col) 是否在矩阵范围内。如果越界，直接返回。 b. 可达性检查 ：检查当前单元格是否已经被标记过 ( reachable[row][col] 为 True)。如果已经标记过，说明已经探索过，直接返回以避免重复计算和无限递归。 c. 高度检查（“逆流”条件） ：这是最关键的一步。我们要模拟水从海洋流过来。 prev_height 是“上游”的高度。当前单元格 heights[row][col] 是“下游”的高度。水只能从高往低流，所以“反向”探索时，我们必须保证“下游”的高度（当前单元格） 不低于 “上游”的高度（ prev_height ），即 heights[row][col] >= prev_height 。如果当前单元格的高度 小于 prev_height ，说明水无法从当前这个低洼处流回到那个高的“上游”点，因此这个方向探索终止，直接返回。 d. 标记当前单元格 ：如果通过了以上所有检查，说明当前单元格可以被“反向”到达。将其在 reachable 矩阵中标记为 True。 e. 递归探索邻居 ：以当前单元格的高度 heights[row][col] 作为新的 prev_height ，递归地调用DFS函数，探索其上、下、左、右四个方向的邻居单元格。 步骤三：主算法流程 现在我们将DFS函数应用到整个问题上。 初始化 ： 获取矩阵的行数 m 和列数 n 。 创建两个大小均为 m x n 的布尔矩阵 pacific_reachable 和 atlantic_reachable ，初始值全部为 False。 从太平洋边界开始DFS ： 太平洋边界 是第一行（row = 0）和第一列（col = 0）的所有单元格。 对于第一行的每一个单元格 (0, col)，调用 dfs(0, col, pacific_reachable, heights[0][col]) 。注意，这里的 prev_height 初始值就是边界单元格自身的高度。因为海洋是起点，我们认为水从海洋（高度为边界单元格高度）流过来。 对于第一列的每一个单元格 (row, 0)，调用 dfs(row, 0, pacific_reachable, heights[row][0]) 。 从大西洋边界开始DFS ： 大西洋边界 是最后一行（row = m-1）和最后一列（col = n-1）的所有单元格。 对于最后一行的每一个单元格 (m-1, col)，调用 dfs(m-1, col, atlantic_reachable, heights[m-1][col]) 。 对于最后一列的每一个单元格 (row, n-1)，调用 dfs(row, n-1, atlantic_reachable, heights[row][n-1]) 。 收集结果 ： 创建一个空列表 result 用于存放结果坐标。 遍历整个矩阵的每一个单元格 (i, j)。 如果 pacific_reachable[i][j] 和 atlantic_reachable[i][j] 都为 True，说明这个单元格的水既能流到太平洋，也能流到大西洋。 将这个单元格的坐标 (i, j) 添加到 result 列表中。 最终返回 result 列表。 总结 这个算法通过“反向思考”，将问题从“每个点能否流到海”转化为“海的水能逆流到哪些点”，极大地降低了计算复杂度。我们通过两次DFS/BFS（一次针对太平洋，一次针对大西洋）来标记可达区域，最后求交集。这种方法的时间复杂度和空间复杂度都是 O(m * n)，其中 m 和 n 是矩阵的尺寸。