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

字数 1529 2025-10-28 08:36:45

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

题目描述

有一个 m x n 的矩形岛屿，其左上角毗邻太平洋，右下角毗邻大西洋。该岛屿被划分为多个小方格，每个方格 heights[i][j] 表示该地点的高度。水流可以沿上、下、左、右四个方向流动，且只能从高处或等高处流向低处。请找出那些地点，其水流既能流向太平洋，也能流向大西洋。返回所有满足条件的地点的坐标（顺序不限）。

解题思路

这个问题不是从一个点出发去寻找另一个点，而是要找出所有能同时到达两个“终点”（即海洋）的起点。直接对每个格子进行搜索（比如BFS或DFS）来判断是否能同时到达两大洋，效率会很低（O(m²n²)）。

一个更巧妙的思路是逆向思考：从两大洋的边界出发，逆向（即从低处流向高处，或者说水可以流过来的反方向）进行搜索，标记所有能够到达的点。那么，既能被太平洋边界逆向到达，又能被大西洋边界逆向到达的点，就是我们要找的答案。

解题步骤

初始化：
- 创建两个大小和地图一样的布尔矩阵（或集合），分别命名为 pacific 和 atlantic。pacific[i][j] = True 表示坐标 (i, j) 能被太平洋边界逆向到达。
- 准备一个队列（用于BFS）或使用递归栈（用于DFS）。
从太平洋边界开始逆向搜索（BFS/DFS）：
- 边界定义： 太平洋在左上角，所以所有第一行的格子（上边界）和第一列的格子（左边界）都毗邻太平洋。
- 搜索过程： 将这些边界格子作为起点，加入队列（或开始DFS）。对于每个出队的格子 (i, j)，检查它的四个邻居 (x, y)。
- 逆向流动条件： 因为我们是逆向搜索（模拟水“流回来”），所以条件应该是：如果邻居 (x, y) 的高度 大于等于 当前格子 (i, j) 的高度（即 heights[x][y] >= heights[i][j]），并且邻居 (x, y) 还没有被标记为 pacific，那么这个邻居 (x, y) 的水就可以“流回”到当前格子，最终汇入太平洋。因此，我们将 (x, y) 标记为 pacific，并将其加入队列，继续搜索。
- 此过程持续到队列为空，此时 pacific 矩阵标记了所有能流向太平洋的格子。
从大西洋边界开始逆向搜索（BFS/DFS）：
- 边界定义： 大西洋在右下角，所以所有最后一行的格子（下边界）和最后一列的格子（右边界）都毗邻大西洋。
- 搜索过程： 与第二步完全对称。将这些边界格子作为起点，进行BFS/DFS。
- 逆向流动条件： 同样，检查邻居 (x, y) 的高度是否 大于等于 当前格子 (i, j) 的高度（heights[x][y] >= heights[i][j]），并且邻居尚未被标记为 atlantic。满足条件则标记并加入队列。
- 此过程持续到队列为空，此时 atlantic 矩阵标记了所有能流向大西洋的格子。
收集结果：
- 遍历整个地图的每一个格子 (i, j)。
- 如果发现 pacific[i][j] 和 atlantic[i][j] 都为 True，说明这个格子的水既能流向太平洋，也能流向大西洋。
- 将这个格子的坐标 (i, j) 加入结果列表。
返回结果列表。

总结

这个算法的核心是 “多源点BFS/DFS” 和 “逆向思维”。通过从已知的终点（海洋边界）反向扩散，我们避免了为每个起点进行重复的搜索，将时间复杂度优化到了 O(m * n)，因为每个格子最多被每个海洋的BFS/DFS访问一次。这种方法在处理这种“可达性”问题时非常高效。

LeetCode 417. 太平洋大西洋水流问题题目描述有一个 m x n 的矩形岛屿，其左上角毗邻太平洋，右下角毗邻大西洋。该岛屿被划分为多个小方格，每个方格 heights[i][j] 表示该地点的高度。水流可以沿上、下、左、右四个方向流动，且只能从高处或等高处流向低处。请找出那些地点，其水流既能流向太平洋，也能流向大西洋。返回所有满足条件的地点的坐标（顺序不限）。解题思路这个问题不是从一个点出发去寻找另一个点，而是要找出所有能同时到达两个“终点”（即海洋）的起点。直接对每个格子进行搜索（比如BFS或DFS）来判断是否能同时到达两大洋，效率会很低（O(m²n²)）。一个更巧妙的思路是逆向思考：从两大洋的边界出发，逆向（即从低处流向高处，或者说水可以流过来的反方向）进行搜索，标记所有能够到达的点。那么，既能被太平洋边界逆向到达，又能被大西洋边界逆向到达的点，就是我们要找的答案。解题步骤初始化：创建两个大小和地图一样的布尔矩阵（或集合），分别命名为 pacific 和 atlantic 。 pacific[i][j] = True 表示坐标 (i, j) 能被太平洋边界逆向到达。准备一个队列（用于BFS）或使用递归栈（用于DFS）。从太平洋边界开始逆向搜索（BFS/DFS）：边界定义：太平洋在左上角，所以所有第一行的格子（上边界）和第一列的格子（左边界）都毗邻太平洋。搜索过程：将这些边界格子作为起点，加入队列（或开始DFS）。对于每个出队的格子 (i, j) ，检查它的四个邻居 (x, y) 。逆向流动条件：因为我们是逆向搜索（模拟水“流回来”），所以条件应该是：如果邻居 (x, y) 的高度大于等于当前格子 (i, j) 的高度（即 heights[x][y] >= heights[i][j] ），并且邻居 (x, y) 还没有被标记为 pacific ，那么这个邻居 (x, y) 的水就可以“流回”到当前格子，最终汇入太平洋。因此，我们将 (x, y) 标记为 pacific ，并将其加入队列，继续搜索。此过程持续到队列为空，此时 pacific 矩阵标记了所有能流向太平洋的格子。从大西洋边界开始逆向搜索（BFS/DFS）：边界定义：大西洋在右下角，所以所有最后一行的格子（下边界）和最后一列的格子（右边界）都毗邻大西洋。搜索过程：与第二步完全对称。将这些边界格子作为起点，进行BFS/DFS。逆向流动条件：同样，检查邻居 (x, y) 的高度是否大于等于当前格子 (i, j) 的高度（ heights[x][y] >= heights[i][j] ），并且邻居尚未被标记为 atlantic 。满足条件则标记并加入队列。此过程持续到队列为空，此时 atlantic 矩阵标记了所有能流向大西洋的格子。收集结果：遍历整个地图的每一个格子 (i, j) 。如果发现 pacific[i][j] 和 atlantic[i][j] 都为 True ，说明这个格子的水既能流向太平洋，也能流向大西洋。将这个格子的坐标 (i, j) 加入结果列表。返回结果列表。总结这个算法的核心是 “多源点BFS/DFS” 和 “逆向思维” 。通过从已知的终点（海洋边界）反向扩散，我们避免了为每个起点进行重复的搜索，将时间复杂度优化到了 O(m * n)，因为每个格子最多被每个海洋的BFS/DFS访问一次。这种方法在处理这种“可达性”问题时非常高效。