LeetCode 第417题：太平洋大西洋水流问题

📖 文章摘要

本文详细解析LeetCode第417题“太平洋大西洋水流问题”，这是一道图搜索问题。文章提供了基于DFS和BFS的两种解题思路，包含C#、Python、C++三种语言实现，配有详细的图解和性能分析。适合正在学习图论算法的程序员。

核心知识点： DFS、BFS、矩阵遍历、图搜索
难度等级： 中等
推荐人群： 具有基础算法知识，想要深入学习图搜索算法的程序员

题目描述

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 太平洋 处于大陆的左边界和上边界，而 大西洋 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。

示例

示例 1：

太平洋大西洋水流

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
解释: 上图表示高度矩阵，箭头表示水流方向。
在这里，蓝色单元格表示雨水可以流向太平洋，红色单元格表示雨水可以流向大西洋，紫色单元格表示雨水既可以流向太平洋也可以流向大西洋。

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105

解题思路

这道题可以使用DFS或BFS来解决。关键思路是从海洋边界开始反向搜索，找到所有可以流向该海洋的点。

关键点：

从太平洋边界（左边和上边）开始搜索
从大西洋边界（右边和下边）开始搜索
找到两个搜索结果的交集
注意搜索时是从低处往高处搜索

图解思路

搜索方向分析表

边界	起始位置	搜索方向	说明
太平洋	左边界和上边界	四个方向	从低到高搜索
大西洋	右边界和下边界	四个方向	从低到高搜索

状态转移表

当前位置	下一位置	是否可达	说明
(i,j)	(i±1,j) 或 (i,j±1)	heights[next] >= heights[curr]	水可以从低处流向高处
边界	出界	false	停止搜索
已访问	-	false	避免重复访问

代码实现

C# 实现

public class Solution {
    private int[][] heights;
    private int m, n;
    private int[][] directions = new int[][] {
        new int[] {-1, 0}, new int[] {1, 0}, 
        new int[] {0, -1}, new int[] {0, 1}
    };
    
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        this.heights = heights;
        this.m = heights.Length;
        this.n = heights[0].Length;
        
        bool[,] pacific = new bool[m,n];
        bool[,] atlantic = new bool[m,n];
        
        // 从太平洋边界开始DFS
        for (int i = 0; i < m; i++) DFS(i, 0, pacific);
        for (int j = 0; j < n; j++) DFS(0, j, pacific);
        
        // 从大西洋边界开始DFS
        for (int i = 0; i < m; i++) DFS(i, n-1, atlantic);
        for (int j = 0; j < n; j++) DFS(m-1, j, atlantic);
        
        // 找到交集
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i,j] && atlantic[i,j]) {
                    result.Add(new List<int> {i, j});
                }
            }
        }
        
        return result;
    }
    
    private void DFS(int row, int col, bool[,] visited) {
        visited[row,col] = true;
        
        foreach (var dir in directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n 
                && !visited[newRow,newCol] 
                && heights[newRow][newCol] >= heights[row][col]) {
                DFS(newRow, newCol, visited);
            }
        }
    }
}

Python 实现

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights:
            return []
            
        m, n = len(heights), len(heights[0])
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        
        def dfs(row: int, col: int, visited: set) -> None:
            visited.add((row, col))
            
            for dx, dy in directions:
                new_row, new_col = row + dx, col + dy
                
                if (0 <= new_row < m and 0 <= new_col < n and 
                    (new_row, new_col) not in visited and
                    heights[new_row][new_col] >= heights[row][col]):
                    dfs(new_row, new_col, visited)
        
        pacific = set()
        atlantic = set()
        
        # 从太平洋边界开始DFS
        for i in range(m):
            dfs(i, 0, pacific)
        for j in range(n):
            dfs(0, j, pacific)
            
        # 从大西洋边界开始DFS
        for i in range(m):
            dfs(i, n-1, atlantic)
        for j in range(n):
            dfs(m-1, j, atlantic)
            
        # 返回交集
        return list(pacific & atlantic)

C++ 实现

class Solution {
private:
    vector<vector<int>> heights;
    int m, n;
    vector<vector<int>> directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    
    void dfs(int row, int col, vector<vector<bool>>& visited) {
        visited[row][col] = true;
        
        for (const auto& dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n 
                && !visited[newRow][newCol] 
                && heights[newRow][newCol] >= heights[row][col]) {
                dfs(newRow, newCol, visited);
            }
        }
    }
    
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        if (heights.empty()) return {};
        
        this->heights = heights;
        this->m = heights.size();
        this->n = heights[0].size();
        
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        
        // 从太平洋边界开始DFS
        for (int i = 0; i < m; i++) dfs(i, 0, pacific);
        for (int j = 0; j < n; j++) dfs(0, j, pacific);
        
        // 从大西洋边界开始DFS
        for (int i = 0; i < m; i++) dfs(i, n-1, atlantic);
        for (int j = 0; j < n; j++) dfs(m-1, j, atlantic);
        
        // 找到交集
        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        
        return result;
    }
};

执行结果

C# 实现

执行用时：248 ms
内存消耗：45.2 MB

Python 实现

执行用时：284 ms
内存消耗：17.8 MB

C++ 实现

执行用时：32 ms
内存消耗：17.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	248 ms	45.2 MB	性能中等，内存占用较大
Python	284 ms	17.8 MB	执行最慢，内存占用适中
C++	32 ms	17.4 MB	执行最快，内存占用最小

代码亮点

🎯 使用DFS从边界开始反向搜索，避免了从每个点开始搜索的复杂度
💡 使用方向数组简化了四个方向的搜索代码
🔍 通过两个visited数组/集合分别记录可以到达两个海洋的点
🎨 三种语言实现保持了相同的算法思路，便于对比学习

常见错误分析

🚫 搜索方向写反，应该是从低处往高处搜索
🚫 忘记处理边界条件，导致数组越界
🚫 visited数组初始化错误
🚫 没有正确处理空输入的情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS	O(m×n)	O(m×n)	代码简洁，易于实现	递归调用可能栈溢出
BFS	O(m×n)	O(m×n)	避免递归调用	需要额外的队列空间
暴力解法	O(m×n×(m+n))	O(1)	思路简单	时间复杂度高

📖 系列导航

🔥 LeetCode 题解合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第417题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

搜索方向分析表

状态转移表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流