417. 太平洋大西洋水流问题（Pacific Atlantic Water Flow）
难度：中等 | 主题：图论、DFS、BFS、多源扩散
题目
有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。太平洋在左边界和上边界，大西洋在右边界和下边界。给定一个 m x n 的整数矩阵 heights，返回网格坐标 result 的列表，其中雨水可以从该坐标流向太平洋和大西洋。
示例
输入：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]]
思路
先讲个故事：水往低处流，反着找水源
你站在山顶，想知道雨水会流向哪片海洋。
水往低处流——但你反着想：从海洋边界往高处走，能走到的地方就是水能流回来的地方。
太平洋：从上边和左边边界出发，往高处走。
大西洋：从下边和右边边界出发，往高处走。
交集：两个海洋都能流到的格子。
引导式推导：反向 DFS
核心洞察： 反向思维。不是从中间往两边流，而是从两个海洋边界往高处流。
flowchart TD A["太平洋边界（上+左）"] --> B["DFS 往高处走"] B --> C["标记 pacific[i][j] = True"] D["大西洋边界（下+右）"] --> E["DFS 往高处走"] E --> F["标记 atlantic[i][j] = True"] C --> G["找交集: pacific[i][j] AND atlantic[i][j]"] F --> G
反向 DFS 的条件： heights[nx][ny] >= heights[x][y]（往高处或等高走），因为从边界逆行向高坡找水源。
代码
class Solution:
def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
m, n = len(heights), len(heights[0])
pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]
def dfs(i: int, j: int, visited: list[list[bool]], prev_height: int):
if i < 0 or i >= m or j < 0 or j >= n:
return
if visited[i][j]:
return
if heights[i][j] < prev_height:
return
visited[i][j] = True
dfs(i + 1, j, visited, heights[i][j])
dfs(i - 1, j, visited, heights[i][j])
dfs(i, j + 1, visited, heights[i][j])
dfs(i, j - 1, visited, heights[i][j])
for i in range(m):
dfs(i, 0, pacific, heights[i][0])
dfs(i, n - 1, atlantic, heights[i][n - 1])
for j in range(n):
dfs(0, j, pacific, heights[0][j])
dfs(m - 1, j, atlantic, heights[m - 1][j])
return [[i, j] for i in range(m) for j in range(n) if pacific[i][j] and atlantic[i][j]]
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(m*n) | 每个格子最多被两个 DFS 各访问一次 |
| 空间 | O(m*n) | 递归栈 + 两个 visited 数组 |
实战考量
频率分析
出现在：字节/美团 图论题，约 20% 常会考到。考察反向思维和多边界处理。
延伸思考
Q：正向从每个格子往两边流可以吗？
A：可以，但每个格子都 DFS 是 O((m*n)²)，太慢。
Q：BFS 可以吗？
A：可以，用队列代替递归，逻辑一样。
Q：如果矩阵很大，递归栈溢出怎么办？
A：用 BFS 或显式栈。
Q：反向 DFS 的比较条件为什么是 heights[i][j] < prev_height 时返回？
A：反向时当前高度必须 >= 前一个高度，才能「逆流而上」。
易错点
-
反向 DFS 的比较条件是
<时返回（即要求>=才继续） -
两次 DFS 分别从两个海洋的边界出发
-
最后找交集
生活类比
水往低处流，反着找水源
站在山顶，不知道雨水会流向哪片海洋。
反着想：从太平洋边界往高处走，能走到的地方 = 水能流回来的地方。
大西洋同理。
两个集合的交集 = 两个海洋都能流到的格子。
反向思维：从目标出发逆推，比正向枚举快得多。
相关题目
| 题目 | 关系 |
|---|---|
| 130被围绕的区域 | 类似多边界扩散 |
| 200岛屿数量 | 连通块计数 |
| 695岛屿的最大面积 | 连通块面积 |
| 417太平洋大西洋水流问题 | 本题 |
→ 返回题单：LeetCode学习路线图 > 十二、图论
速记卡（面试闪卡）
Q1：一句话讲清「417. 太平洋大西洋水流问题（Pacific Atlantic Water Flow）」到底是什么？
A：太平洋大西洋水流问题是求矩阵中能同时流向太平洋和大西洋两大洋的格子集合的反向 DFS 题。
Q2：题目 —— 怎么理解？
A：像判断山顶雨水最终流进哪片海：m×n 岛屿，太平洋贴左/上边界、大西洋贴右/下边界，求哪些格子雨水能同时流进两大洋。Pacific Atlantic Water Flow（太平洋大西洋水流）。
Q3：思路 —— 怎么理解？
A：像反着找水源：水往低处流，但从海洋边界往高处（或等高）逆行，能走到的格子就是水能流回该洋的地方；两个洋各做一次，取交集。Reverse DFS（反向深度优先搜索）。
Q4：代码 —— 怎么理解？
A：像从海岸线向内陆爬坡：用两个 visited 数组，分别从太平洋边界（上+左）和大西洋边界（下+右）出发 DFS，条件 heights[ny] >= 前高，最后收集两数组都为真的格子。DFS（深度优先搜索）。
Q5：复杂度 —— 怎么理解？
A：像数两遍格子：时间 O(m×n)（每个格子最多被两次 DFS 各访问一次），空间 O(m×n)（递归栈 + 两个 visited 数组）。Time/Space Complexity（时间与空间复杂度）。
Q6：核心速记主线有哪些？
-
题目：求能同时流入太平洋和大西洋的格子
-
思路：反向 DFS，从两大洋边界往高处走取交集
-
代码：两 visited 数组，条件 heights[ny] >= 前高
-
复杂度：时间 O(mn)，空间 O(mn)
口诀
A：太平洋贴左上边，大西洋贴右下边
反向逆流往高处，能到便是可流还
两洋各走一遍 DFS，取交集得答案现
比较须用大于等于，莫把方向搞反了