LeetCode 417. 太平洋大西洋水流问题 题目描述 给定一个 m x n 的非负整数矩阵，每个单元格中的值代表该位置的高度。矩阵的左边界和上边界是“太平洋”，右边界和下边界是“大西洋”。水可以从一个单元格流向相邻（上下左右）的高度 小于或等于 当前单元格的单元格。请找出所有既能流向太平洋，又能流向大西洋的单元格的坐标。 解题过程 这个问题可以被看作是两个独立的“水流”问题：一个从太平洋边界（左、上）开始反向追溯（即水从低处流向高处，但我们的搜索方向是从边界向内，沿着高度递增的方向），另一个从大西洋边界（右、下）开始反向追溯。一个单元格如果同时能被太平洋的“水流”和大西洋的“水流”到达，那么它就符合要求。 我们将使用 广度优先搜索（BFS） 来解决这个问题。BFS非常适合这种从多个起点开始，探索可达区域的问题。 步骤 1：定义搜索方向和数据准备 我们有两个目标：标记所有能被太平洋水流到达的单元格，以及所有能被大西洋水流到达的单元格。 我们将创建两个与原始矩阵同样大小的布尔矩阵（或集合）： canReachPacific[m][n] : 用于记录该单元格是否能被太平洋的水流到达。 canReachAtlantic[m][n] : 用于记录该单元格是否能被大西洋的水流到达。 搜索的“流向”是反向的。通常我们考虑水从高往低流。但为了计算方便，我们从海洋边界开始，想象水流是 逆流而上 （即从海洋边界向内陆，只能流向高度 更高或相等 的单元格）。这样，所有能被“逆流”访问到的点，都意味着正方向（从高到低）的水可以从该点流到海洋。 步骤 2：为太平洋执行 BFS 初始化队列 ：将所有与太平洋直接相邻的单元格（即第一列的所有行和第一行的所有列）加入太平洋的BFS队列。同时，在 canReachPacific 矩阵中将这些单元格标记为 True 。 BFS遍历 ： 当队列不为空时，从队列中取出一个单元格 (row, col) 。 检查这个单元格的四个邻居：上 (row-1, col) 、下 (row+1, col) 、左 (row, col-1) 、右 (row, col+1) 。 对于每个邻居单元格，需要检查： a. 坐标是否在矩阵范围内。 b. 该邻居是否 尚未 被标记为 canReachPacific 为 True （避免重复访问）。 c. 最重要的条件：邻居单元格的高度必须 大于或等于 当前单元格 (row, col) 的高度。这是因为我们是在“逆流而上”，水只能从海洋流向高度更高或相同的地方。 如果满足以上所有条件，说明水流可以从太平洋“逆流”到达这个邻居。我们将这个邻居单元格标记为 canReachPacific 为 True ，并将其加入队列，继续搜索。 步骤 3：为大西洋执行 BFS 这个过程与步骤 2 完全对称。 初始化队列 ：将所有与大西洋直接相邻的单元格（即最后一列的所有行和最后一行的所有列）加入大西洋的BFS队列。同时，在 canReachAtlantic 矩阵中将这些单元格标记为 True 。 BFS遍历 ：逻辑与太平洋的BFS完全相同。检查邻居，如果邻居高度 >= 当前单元格高度，且未被访问过，则标记并加入队列。 步骤 4：合并结果 经过步骤 2 和 3 后，我们得到了两个完整的标记矩阵。 我们需要找出所有同时满足 canReachPacific[i][j] == True 且 canReachAtlantic[i][j] == True 的单元格 (i, j) 。 遍历整个矩阵，将满足上述条件的单元格坐标加入结果列表。 返回这个结果列表。 总结 这个算法的核心在于 从边界开始进行反向的BFS 。我们不是从每个内陆点出发去模拟水流能否到达海洋（那样会非常低效），而是从海洋的边界出发，一次性找出所有能被海洋“覆盖”的点。最后，两个海洋“覆盖”区域的交集就是我们的答案。这种方法将时间复杂度从 O(m²n²) 降低到了 O(mn)，因为每个单元格最多被每个海洋的BFS访问一次。