从海洋到陆地：如何找到流向两大洋的雨水路径？🌊🌧️

问题背景：当雨水遇见两大洋

想象这样一个场景：一个美丽的矩形岛屿被太平洋和大西洋环绕。太平洋守护在岛屿的左边界和上边界，而大西洋则拥抱岛屿的右边界和下边界。岛上的雨水会从高处流向低处，最终汇入海洋。

现在，我们需要找出岛上哪些位置的雨水能够同时流向太平洋和大西洋。这不仅是一个有趣的现实问题，更是一个经典的算法挑战！

问题形式化

给定一个 m × n 的网格 heights，其中：

  • heights[r][c] 表示坐标 (r, c) 处的高度
  • 雨水可以从一个单元格流向相邻的四个方向（上、下、左、右）
  • 流动条件：相邻单元格的高度 ≤ 当前单元格的高度
  • 靠近海洋的单元格可以直接流入海洋

我们需要返回所有既能流向太平洋又能流向大西洋的单元格坐标。

解决思路：逆向思维的力量 💡

最直观的想法可能是对每个单元格检查是否能同时到达两个海洋，但这样效率太低。我们采用更聪明的逆向思维：

与其从山顶找海洋，不如从海洋找山顶！

  1. 标记太平洋可达区域：从所有太平洋边界点出发，逆向寻找所有能流入太平洋的单元格
  2. 标记大西洋可达区域：从所有大西洋边界点出发，逆向寻找所有能流入大西洋的单元格
  3. 求交集：找出同时被两个海洋标记的单元格

算法实现详解

核心代码结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    // 定义四个移动方向：上、下、左、右
    static int[][] Dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // 初始化标记数组
        // 从边界开始DFS标记
        // 收集结果
    }
    
    private void dfs(int row, int col, boolean[][] ocean, 
                    int m, int n, int[][] heights) {
        // DFS递归标记可达单元格
    }
}

分步解析

第一步：初始化标记数组

1
2
3
4
int m = heights.length;
int n = heights[0].length;
boolean[][] pacific = new boolean[m][n];  // 标记太平洋可达
boolean[][] atlantic = new boolean[m][n]; // 标记大西洋可达

第二步：从边界开始洪水填充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 标记太平洋：从左边界和上边界开始
for (int i = 0; i < m; i++) {
    dfs(i, 0, pacific, m, n, heights);  // 第一列
}
for (int j = 0; j < n; j++) {
    dfs(0, j, pacific, m, n, heights);  // 第一行
}

// 标记大西洋：从右边界和下边界开始  
for (int k = 0; k < m; k++) {
    dfs(k, n - 1, atlantic, m, n, heights);  // 最后一列
}
for (int l = 0; l < n; l++) {
    dfs(m - 1, l, atlantic, m, n, heights);  // 最后一行
}

第三步：DFS核心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void dfs(int row, int col, boolean[][] ocean, 
                int m, int n, int[][] heights) {
    if (ocean[row][col]) return;  // 已访问过，直接返回
    
    ocean[row][col] = true;  // 标记当前单元格为可达
    
    // 尝试四个方向
    for (int[] dir : Dir) {
        int newRow = row + dir[0];
        int newCol = col + dir[1];
        
        // 检查边界条件和高度条件
        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n 
            && heights[newRow][newCol] >= heights[row][col]) {
            dfs(newRow, newCol, ocean, m, n, heights);
        }
    }
}

第四步：收集最终结果

1
2
3
4
5
6
7
8
9
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (pacific[i][j] && atlantic[i][j]) {
            res.add(Arrays.asList(i, j));  // 添加满足条件的坐标
        }
    }
}
return res;

复杂度分析 📊

  • 时间复杂度：O(m × n)

    • 每个单元格最多被访问4次（每个海洋标记2次）
    • DFS的递归深度最多为网格对角线长度

  • 空间复杂度：O(m × n)

    • 两个标记数组占用 O(m × n) 空间
    • DFS递归栈深度最多为 O(m × n)

实际应用场景 🌍

这种算法思想不仅适用于雨水流动问题，还可以应用于：

  1. 洪水淹没模拟：预测洪水蔓延范围
  2. 图像处理中的区域填充：Photoshop中的魔术棒工具
  3. 游戏地图探索：战争迷雾的揭开机制
  4. 网络连通性检测：判断节点是否连通

优化技巧与变体 🚀

  1. BFS替代DFS：对于极大网格，使用BFS可避免栈溢出
  2. 并行处理：两个海洋的标记可以并行进行
  3. 内存优化：使用位图压缩标记数组
  4. 动态规划变体：记录每个单元格到两个海洋的可达性

总结

通过这个问题的解决，我们学到了：

✅ 逆向思维的威力：从目标反推路径往往更高效
✅ DFS/BFS的灵活应用：洪水填充算法的经典案例
✅ 空间换时间的策略：使用标记数组提高效率
✅ 问题分解的技巧：将复杂问题拆解为多个简单子问题