LeetCode 题解工作台
太平洋大西洋水流问题
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以从太平洋和大西洋的边界出发，分别进行广度优先搜索（BFS），找到所有能够流向太平洋和大西洋的单元格。最后，我们取两个结果的交集，即为既能流向太平洋又能流向大西洋的单元格。 具体地，我们定义一个队列 来存储所有与太平洋相邻的单元格，并定义一个布尔矩阵 来记录哪些单元格能够流向太平洋。类似地，我们定义队列 和布尔矩阵 来处理大西洋。初始时，我们将所有与太平洋相邻的单元格加入队列 ，并将…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
示例 1：
输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：
输入: heights = [[2,1],[1,2]] 输出: [[0,0],[0,1],[1,0],[1,1]]
提示：
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105
解题思路
方法一：BFS
我们可以从太平洋和大西洋的边界出发，分别进行广度优先搜索（BFS），找到所有能够流向太平洋和大西洋的单元格。最后，我们取两个结果的交集，即为既能流向太平洋又能流向大西洋的单元格。
具体地，我们定义一个队列 来存储所有与太平洋相邻的单元格，并定义一个布尔矩阵 来记录哪些单元格能够流向太平洋。类似地，我们定义队列 和布尔矩阵 来处理大西洋。初始时，我们将所有与太平洋相邻的单元格加入队列 ，并将它们在 中标记为已访问。同样地，将所有与大西洋相邻的单元格加入队列 ，并在 中标记为已访问。
然后，我们分别对 和 进行 BFS。在每次 BFS 中，我们从队列中取出一个单元格 ，并检查它的四个相邻单元格 。如果相邻单元格在矩阵范围内，且未被访问过，并且其高度不小于当前单元格的高度（即水可以流向该单元格），我们将其加入队列并标记为已访问。
最后，我们遍历整个矩阵，找出同时在 和 中被标记为已访问的单元格，这些单元格即为答案。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
def bfs(q: Deque[Tuple[int, int]], vis: List[List[bool]]) -> None:
while q:
x, y = q.popleft()
for dx, dy in pairwise(dirs):
nx, ny = x + dx, y + dy
if (
0 <= nx < m
and 0 <= ny < n
and not vis[nx][ny]
and heights[nx][ny] >= heights[x][y]
):
vis[nx][ny] = True
q.append((nx, ny))
m, n = len(heights), len(heights[0])
vis1 = [[False] * n for _ in range(m)]
vis2 = [[False] * n for _ in range(m)]
q1: Deque[Tuple[int, int]] = deque()
q2: Deque[Tuple[int, int]] = deque()
dirs = (-1, 0, 1, 0, -1)
for i in range(m):
q1.append((i, 0))
vis1[i][0] = True
q2.append((i, n - 1))
vis2[i][n - 1] = True
for j in range(n):
q1.append((0, j))
vis1[0][j] = True
q2.append((m - 1, j))
vis2[m - 1][j] = True
bfs(q1, vis1)
bfs(q2, vis2)
return [(i, j) for i in range(m) for j in range(n) if vis1[i][j] and vis2[i][j]]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The problem requires familiarity with DFS/BFS traversal techniques and understanding grid-based problems.
- question_mark
A candidate should demonstrate the ability to efficiently mark cells that can flow to both oceans.
- question_mark
Look for candidates who understand the trade-offs between DFS and BFS, particularly with respect to space optimization.
常见陷阱
外企场景- error
Not considering edge cases, such as the smallest grid or a single row/column island.
- error
Confusing the direction of flow – ensure that water can flow in all four directions (up, down, left, right).
- error
Misunderstanding the intersection of reachable cells for both oceans – both DFS/BFS must be executed separately for each ocean before finding the overlap.
进阶变体
外企场景- arrow_right_alt
What if the grid is much larger? Consider optimizing the space usage or processing multiple test cases efficiently.
- arrow_right_alt
What if diagonal movement is allowed for water flow? Adjust the DFS/BFS approach to account for diagonal directions.
- arrow_right_alt
What if there are additional height constraints for the water flow? Modify the DFS/BFS to account for specific thresholds for height differences.