题目描述
思路解析动画文字版
从每个格子往海里 DFS 会重复很多次。
反过来从两片海的边界出发，只能走到更高或相等的格子；两次可达集合取交集。
① 反向思维：从海边界往「高处」爬：水从高往低、平地流。反过来想：从一片海的边界出发，往「不低于自己」的格子爬，爬得到的格子就能把水流到这片海。先看太平洋＝上边界＋左边界。
② 太平洋反向 BFS：爬向 ≥ 当前高度的邻居：从边界往高处扩展：中心 (1,1)=3 能从 (0,1)=2 或 (1,0)=2 爬上来(3 ≥ 2) → 太平洋可达。左上三角连同中间这条「脊」都能到。
③ 太平洋可达 = 左上区域 + 中脊（6 格）：太平洋集合 ＝ {(0,0),(0,1),(0,2),(1,0),(2,0),(1,1)}。(1,2)、(2,1)、(2,2) 太低，爬不到太平洋那侧的边界。
④ 大西洋反向 BFS（下边界 + 右边界）：同理从大西洋(下边界＋右边界)反向往高处爬，得到 {(2,2),(2,1),(1,2),(2,0),(1,1),(0,2)} ＝ 右下区域 + 中脊。
⑤ 交集 ＝ 两洋都能到 ＝ 反对角线：两集合的交集 ＝ {(0,2),(1,1),(2,0)} —— 正是这条反对角线的脊，水能同时流向两片海。答案就是这 3 个坐标。
一句话记住：反过来从两片海的边界出发，只能走到更高或相等的格子；两次可达集合取交集。
边界三连：本题真边界：单行列、平地、1×1。
⑥ 为什么反向？正向从每格各搜一次会爆：若正向从每个格子各跑一次 DFS 看能否到海，是 O((m·n)²)。反向只需从两片海边界各跑一次 BFS、每格访问 O(1)，O(m·n) 搞定。爬的条件是「邻居 ≥ 当前」——因为正向水是高→低流，反过来就是低→高爬。
面试追问 · 核心思路：思路：从两片海边界反向 BFS 爬高，求两可达集的交集。
面试追问 · 为何条件是邻居≥当前：正向高→低流，反向就是低→高爬，故邻居 ≥ 当前。
面试追问 · 复杂度：复杂度：两次 BFS 各 O(m·n)，空间 O(m·n)。
这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问「反向 BFS 的爬高条件为什么是 ≥」。
参考代码
class Solution: def pacificAtlantic(self, heights): rows, cols = len(heights), len(heights[0]) def bfs(starts): seen = set(starts) q = list(starts) for r, c in q: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]: seen.add((nr, nc)) q.append((nr, nc)) return seen pac = [(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)] atl = [(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)] return [list(x) for x in bfs(pac) & bfs(atl)]复杂度
- 时间复杂度：O(m·n)，两片海各一次 BFS，每格最多访问一次
- 空间复杂度：O(m·n)，两个 visited 集合 + 队列
可套用的代码模板
记牢：从两片海边界反向 BFS、沿 ≥ 爬高、求两可达集交集。
Python
# 反向双源 BFS 骨架def bfs(starts): # 从某片海的边界出发 seen = set(starts); q = list(starts) for r, c in q: for nr, nc in 四邻(r, c): if 越界 or (nr,nc) in seen: continue if heights[nr][nc] >= heights[r][c]: # 反向爬高 seen.add((nr,nc)); q.append((nr,nc)) return seenpac = 上边界 + 左边界; atl = 下边界 + 右边界return bfs(pac) & bfs(atl) # 两洋可达集取交集易错点
面试追问把动画讲成自己的话
追问整体思路是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
被围绕的区域
LeetCode 130 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题