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

这道题到底在问什么

输入

5×5 高度矩阵

输出

7 个格子

最优解：一步一步想明白

1. 3记住这个反向：正向「水往低走」== 反向「从海边往高爬」。
2. 4先爬太平洋：起点是上边一整行 + 左边一整列（这些格紧挨太平洋）。
3. 5太平洋爬到 (4,0)高度5，标记可达。接着看它四周更高（≥5）的邻居。
4. 6太平洋爬到 (3,0)高度6，标记可达。接着看它四周更高（≥6）的邻居。
5. 7太平洋爬到 (3,1)高度7，标记可达。接着看它四周更高（≥7）的邻居。
6. 8太平洋爬到 (2,0)高度2，标记可达。接着看它四周更高（≥2）的邻居。
7. 9太平洋爬到 (1,0)高度3，标记可达。接着看它四周更高（≥3）的邻居。
8. 10太平洋爬到 (2,1)高度4，标记可达。接着看它四周更高（≥4）的邻居。
9. 11太平洋爬到 (2,2)高度5，标记可达。接着看它四周更高（≥5）的邻居。
10. 12太平洋爬到 (0,0)高度1，标记可达。接着看它四周更高（≥1）的邻居。
11. 13太平洋爬到 (0,1)高度2，标记可达。接着看它四周更高（≥2）的邻居。
12. 14太平洋爬到 (1,1)高度2，标记可达。接着看它四周更高（≥2）的邻居。
13. 15太平洋爬到 (1,2)高度3，标记可达。接着看它四周更高（≥3）的邻居。
14. 16太平洋爬到 (1,3)高度4，标记可达。接着看它四周更高（≥4）的邻居。
15. 17太平洋爬到 (1,4)高度4，标记可达。接着看它四周更高（≥4）的邻居。
16. 18太平洋爬到 (0,4)高度5，标记可达。接着看它四周更高（≥5）的邻居。
17. 19太平洋爬到 (0,2)高度2，标记可达。接着看它四周更高（≥2）的邻居。
18. 20太平洋爬到 (0,3)高度3，标记可达。接着看它四周更高（≥3）的邻居。
19. 21太平洋可达的格已标出（共16个）。现在反过来爬大西洋：起点是下边一整行 + 右边一整列。
20. 22大西洋爬到 (4,4)高度4，标记可达。接着看它四周更高（≥4）的邻居。
21. 23大西洋爬到 (3,4)高度5，标记可达。接着看它四周更高（≥5）的邻居。
22. 24大西洋爬到 (2,4)高度1，标记可达。接着看它四周更高（≥1）的邻居。
23. 25大西洋爬到 (1,4)高度4，标记可达。接着看它四周更高（≥4）的邻居。
24. 26大西洋爬到 (0,4)高度5，标记可达。接着看它四周更高（≥5）的邻居。
25. 27大西洋爬到 (1,3)高度4，标记可达。接着看它四周更高（≥4）的邻居。
26. 28大西洋爬到 (2,3)高度3，标记可达。接着看它四周更高（≥3）的邻居。
27. 29大西洋爬到 (3,3)高度4，标记可达。接着看它四周更高（≥4）的邻居。
28. 30大西洋爬到 (2,2)高度5，标记可达。接着看它四周更高（≥5）的邻居。
29. 31大西洋爬到 (4,3)高度2，标记可达。接着看它四周更高（≥2）的邻居。
30. 32大西洋爬到 (4,2)高度1，标记可达。接着看它四周更高（≥1）的邻居。
31. 33大西洋爬到 (3,2)高度1，标记可达。接着看它四周更高（≥1）的邻居。
32. 34大西洋爬到 (3,1)高度7，标记可达。接着看它四周更高（≥7）的邻居。
33. 35大西洋爬到 (4,1)高度1，标记可达。接着看它四周更高（≥1）的邻居。
34. 36大西洋爬到 (4,0)高度5，标记可达。接着看它四周更高（≥5）的邻居。
35. 37大西洋爬到 (3,0)高度6，标记可达。接着看它四周更高（≥6）的邻居。
36. 38两遍爬完。橘=太平洋可达，蓝灰=大西洋可达。重叠的格（两边都标过）就是答案，逐个点亮。
37. 39(0,4)高度5：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。
38. 40(1,3)高度4：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。
39. 41(1,4)高度4：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。
40. 42(2,2)高度5：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。
41. 43(3,0)高度6：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。
42. 44(3,1)高度7：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。
43. 45(4,0)高度5：太平洋✓ 大西洋✓ → 点亮。它的水既能往左上流入太平洋，也能往右下流入大西洋。

⚠️ 容易写错的地方

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

def pacificAtlantic(h):
    R, C = len(h), len(h[0])
    pac, atl = set(), set()
    def dfs(i, j, seen):
        seen.add((i, j))
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ni, nj = i+di, j+dj
            if 0<=ni<R and 0<=nj<C and (ni,nj) not in seen \
               and h[ni][nj] >= h[i][j]:
                dfs(ni, nj, seen)
    for i in range(R): dfs(i,0,pac); dfs(i,C-1,atl)
    for j in range(C): dfs(0,j,pac); dfs(R-1,j,atl)
    return [[i,j] for i in range(R) for j in range(C)
            if (i,j) in pac and (i,j) in atl]

class Solution {
  int R, C;
  void dfs(vector<vector<int>>& h, int i, int j,
           vector<vector<bool>>& seen) {
    seen[i][j] = true;
    int d[5] = {1,0,-1,0,1};
    for (int k = 0; k < 4; k++) {
      int ni = i+d[k], nj = j+d[k+1];
      if (ni>=0&&ni<R&&nj>=0&&nj<C&&!seen[ni][nj]
          && h[ni][nj] >= h[i][j])
        dfs(h, ni, nj, seen);
    }
  }
public:
  vector<vector<int>> pacificAtlantic(
      vector<vector<int>>& h) {
    R = h.size(); C = h[0].size();
    vector<vector<bool>> pac(R, vector<bool>(C));
    vector<vector<bool>> atl(R, vector<bool>(C));
    for (int i = 0; i < R; i++) {
      dfs(h, i, 0, pac); dfs(h, i, C-1, atl);
    }
    for (int j = 0; j < C; j++) {
      dfs(h, 0, j, pac); dfs(h, R-1, j, atl);
    }
    vector<vector<int>> res;
    for (int i = 0; i < R; i++)
      for (int j = 0; j < C; j++)
        if (pac[i][j] && atl[i][j])
          res.push_back({i, j});
    return res;
  }
};

class Solution {
    int R, C;
    int[] d = {1, 0, -1, 0, 1};
    void dfs(int[][] h, int i, int j, boolean[][] seen) {
        seen[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int ni = i + d[k], nj = j + d[k + 1];
            if (ni >= 0 && ni < R && nj >= 0 && nj < C
                && !seen[ni][nj] && h[ni][nj] >= h[i][j])
                dfs(h, ni, nj, seen);
        }
    }
    public List<List<Integer>> pacificAtlantic(int[][] h) {
        R = h.length; C = h[0].length;
        boolean[][] pac = new boolean[R][C];
        boolean[][] atl = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            dfs(h, i, 0, pac); dfs(h, i, C - 1, atl);
        }
        for (int j = 0; j < C; j++) {
            dfs(h, 0, j, pac); dfs(h, R - 1, j, atl);
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (pac[i][j] && atl[i][j])
                    res.add(Arrays.asList(i, j));
        return res;
    }
}

复杂度

面试官可能追问