417. 太平洋大西洋水流问题（中等）

Blind 75 › 417. 太平洋大西洋水流问题（中等） （第 3 章）
文章工具

题目

有一座 m × n 的矩形海岛，每个格子有一个海拔高度 heights[r][c]。雨水落在岛上后，只能向上下左右四个方向中「海拔小于或等于当前格子」的邻居流动；格子紧贴海洋的那一面，可以直接把水排进对应海洋。

规定：太平洋在上边界和左边界，大西洋在右边界和下边界。请返回所有「既能流到太平洋、又能流到大西洋」的格子坐标，每个坐标写成 [r, c]。

自造示例：

heights = [[1,2,3],[2,4,2],[3,2,1]]

行 列012
0123
1242
2321

返回 [[0,2],[1,1],[2,0]]：正中间的 4 能向两侧递减流到两边；(0,2) 能向左上流到太平洋、向右下流到大西洋；(2,0) 同理。左上角 1 到不了大西洋，右下角 1 到不了太平洋。

约束：1 ≤ m, n ≤ 200，0 ≤ heights[r][c] ≤ 105。

思路

一句话本质：把「每个格子能不能流到海」反过来想，从两个海洋边界向陆地做反向泛洪，两个集合的交集就是答案。

最直白的做法：对每个格子都跑一次 DFS / BFS，沿「不上升」的实际水流方向走，分别判断能不能摸到上/左边界，以及能不能摸到下/右边界。

这个做法的问题：一次遍历最坏会走遍整个网格，花费 O(mn)；mn 个格子、每个格子还要分别检查两个海洋，最坏是 O((mn)2)。当 m = n = 200 时，约 4 × 104 × 4 × 104 = 1.6 × 109 次访问，会超时。

关键观察：正向水流是「高流到低或相等」，所以一条从某格子到海的可行路径，反过来看就是从海的边界出发，每一步只能走向「海拔大于等于当前」的格子。这样一条反向路径里的每个点，都是能把水最终送进这片海的点。

于是选定做法：从两片海的边界格子同时出发，各做一次多源反向泛洪，得到「能到太平洋」和「能到大西洋」两个标记矩阵，最后取交集。

做法要跑几次单次代价总代价
逐格正向找海每个格子 × 两个海O(mn)O((mn)²)
两岸反向泛洪两个海各一次O(mn)O(mn)

解法

  1. 为太平洋、大西洋各开一个 visited 矩阵，含义是「该格子能否流到对应海洋」。
  2. 把太平洋的左边界、上边界全部入队并标记；把大西洋的右边界、下边界全部入队并标记。
  3. 对每个海洋做多源 BFS：从当前格向四邻扩展，只有邻居海拔 ≥ 当前格海拔时，才说明「水能从邻居流过来」，入队并标记。
  4. 两轮都完成后，遍历整个网格，把两个 visited 同时为真的坐标加入答案。

下图把上面 4 个步骤串成流程，并逐步演示：

417. 太平洋大西洋水流问题（中等） 解法步骤流程图
图① 解法步骤流程图（共 4 步）。
417. 太平洋大西洋水流问题（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
 int m = heights.size(), n = heights[0].size();
 vector<vector<bool>> pac = flood(heights, true);
 vector<vector<bool>> atl = flood(heights, false);  vector<vector<int>> ans;
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。