LC417
太平洋大西洋水流问题
网格 DFS · 双源可视化:图与网格矩阵找能流到太平洋与大西洋的格子。
时间 O(n)空间 O(1)
题目1 / 6
题目与输入建立输入、目标与算法心智
能流到太平洋/大西洋的格子分别标记
正在加载算法场景...
当前发生了什么
矩阵找能流到太平洋与大西洋的格子。
机器状态
pac/atl 可达集合。
为什么正确
从两大洋边界 DFS 反向标记可达,交集即答案。
不变量
反向沿高度不降 DFS。
面试怎么说
两趟边界 DFS+交集 O(mn)。
人类输入
矩阵找能流到太平洋与大西洋的格子。
机制
从两大洋边界 DFS 反向标记可达,交集即答案。
机器状态
pac/atl 可达集合。
可观察结果
边界交集格子列表。
不变量
- · 反向沿高度不降 DFS。
常见误区
- · 正向从每格 DFS 会重复。
迁移练习
- · LC200 岛屿
- · LC130 被围
面试怎么答
两趟边界 DFS+交集 O(mn)。