太平洋大西洋水流问题 图解题解

这道题到底在问什么

heights

[[1,2,3],[2,3,2],[3,2,1]]

输出

[[0,2],[1,1],[2,0]]（反对角线）

最优解：一步一步想明白

1. 3从每个格子往海里 DFS 会重复很多次。
2. 4反过来从两片海的边界出发，只能走到更高或相等的格子；两次可达集合取交集。
3. 5水从高往低、平地流。反过来想：从一片海的边界出发，往「不低于自己」的格子爬，爬得到的格子就能把水流到这片海。先看太平洋＝上边界＋左边界。
4. 6从边界往高处扩展：中心 (1,1)=3 能从 (0,1)=2 或 (1,0)=2 爬上来(3 ≥ 2) → 太平洋可达。左上三角连同中间这条「脊」都能到。
5. 7太平洋集合 ＝ {(0,0),(0,1),(0,2),(1,0),(2,0),(1,1)}。(1,2)、(2,1)、(2,2) 太低，爬不到太平洋那侧的边界。
6. 8同理从大西洋(下边界＋右边界)反向往高处爬，得到 {(2,2),(2,1),(1,2),(2,0),(1,1),(0,2)} ＝ 右下区域 + 中脊。
7. 9两集合的交集 ＝ {(0,2),(1,1),(2,0)} —— 正是这条反对角线的脊，水能同时流向两片海。答案就是这 3 个坐标。
8. 12一句话记住：反过来从两片海的边界出发，只能走到更高或相等的格子；两次可达集合取交集。
9. 15若正向从每个格子各跑一次 DFS 看能否到海，是 O((m·n)²)。反向只需从两片海边界各跑一次 BFS、每格访问 O(1)，O(m·n) 搞定。爬的条件是「邻居 ≥ 当前」——因为正向水是高→低流，反过来就是低→高爬。
10. 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问「反向 BFS 的爬高条件为什么是 ≥」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def pacificAtlantic(self, heights):
        rows, cols = len(heights), len(heights[0])
        def bfs(starts):
            seen = set(starts)
            q = list(starts)
            for r, c in q:
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]:
                        seen.add((nr, nc))
                        q.append((nr, nc))
            return seen
        pac = [(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)]
        atl = [(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)]
        return [list(x) for x in bfs(pac) & bfs(atl)]

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
        int m = h.size(), n = h[0].size();
        auto bfs = [&](queue<pair<int,int>> q) {
            vector<vector<int>> seen(m, vector<int>(n));
            queue<pair<int,int>> work = q;
            while (!q.empty()) { auto [r,c] = q.front(); q.pop(); seen[r][c] = 1; }
            q = work;
            int d[5] = {1,0,-1,0,1};
            while (!q.empty()) {
                auto [r,c] = q.front(); q.pop();
                for (int k=0;k<4;k++) {
                    int nr=r+d[k], nc=c+d[k+1];
                    if (nr>=0&&nr<m&&nc>=0&&nc<n&&!seen[nr][nc]&&h[nr][nc]>=h[r][c]) {
                        seen[nr][nc]=1; q.push({nr,nc});
                    }
                }
            }
            return seen;
        };
        queue<pair<int,int>> p, a;
        for (int c=0;c<n;c++) { p.push({0,c}); a.push({m-1,c}); }
        for (int r=0;r<m;r++) { p.push({r,0}); a.push({r,n-1}); }
        auto P = bfs(p), A = bfs(a);
        vector<vector<int>> ans;
        for (int r=0;r<m;r++) for (int c=0;c<n;c++) if (P[r][c] && A[r][c]) ans.push_back({r,c});
        return ans;
    }
};

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] h) {
        int m = h.length, n = h[0].length;
        boolean[][] p = bfs(h, true), a = bfs(h, false);
        List<List<Integer>> ans = new ArrayList<>();
        for (int r=0;r<m;r++) for (int c=0;c<n;c++) if (p[r][c] && a[r][c]) ans.add(Arrays.asList(r,c));
        return ans;
    }
    private boolean[][] bfs(int[][] h, boolean pacific) {
        int m=h.length,n=h[0].length;
        boolean[][] seen = new boolean[m][n];
        Queue<int[]> q = new ArrayDeque<>();
        for (int c=0;c<n;c++) add(q,seen,pacific?0:m-1,c);
        for (int r=0;r<m;r++) add(q,seen,r,pacific?0:n-1);
        int[] d={1,0,-1,0,1};
        while(!q.isEmpty()){
            int[] cur=q.poll();
            for(int k=0;k<4;k++){
                int nr=cur[0]+d[k], nc=cur[1]+d[k+1];
                if(nr>=0&&nr<m&&nc>=0&&nc<n&&!seen[nr][nc]&&h[nr][nc]>=h[cur[0]][cur[1]]) add(q,seen,nr,nc);
            }
        }
        return seen;
    }
    private void add(Queue<int[]> q, boolean[][] seen, int r, int c){ if(!seen[r][c]){seen[r][c]=true; q.offer(new int[]{r,c});} }
}

# 反向双源 BFS 骨架
def bfs(starts):                 # 从某片海的边界出发
    seen = set(starts); q = list(starts)
    for r, c in q:
        for nr, nc in 四邻(r, c):
            if 越界 or (nr,nc) in seen: continue
            if heights[nr][nc] >= heights[r][c]:   # 反向爬高
                seen.add((nr,nc)); q.append((nr,nc))
    return seen
pac = 上边界 + 左边界;  atl = 下边界 + 右边界
return bfs(pac) & bfs(atl)       # 两洋可达集取交集

复杂度

面试官可能追问