417. 太平洋大西洋水流问题
题目描述
一座岛屿被划成 m x n 的方格，heights[r][c] 是格子 (r, c) 的海拔。岛的上边缘和左边缘挨着太平洋，下边缘和右边缘挨着大西洋。
雨水落在某格后，可以流向上、下、左、右四个相邻格中海拔不高于当前格的那一格，并可以连续流动。位于边缘的格子可以把水直接排进它所挨着的海洋。
找出所有这样的格子：从它出发的雨水既能到达太平洋，也能到达大西洋。
返回这些格子的坐标列表，每个坐标写成 [r, c]，行列下标都从 0 开始。坐标的先后顺序不限。
示例 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]]
解释：(0,1) 和 (1,0) 同时挨着两片海洋；(0,0) 和 (1,1) 可以流向它们，因此四格全部入选。
数据范围
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
解题思路：逆流广度优先搜索
顺着水流从每个格子出发搜索太慢。反过来想：从海边“逆流而上”，只能走向高度 ≥ 当前的邻格。从太平洋边界做一次多源 BFS，得到能流到太平洋的格子集合 pac；从大西洋边界再做一次得到 atl。两个集合的交集就是答案。
为什么正确
被某次 BFS 标记的格子，都存在一条高度单调不增的路径流向对应的海洋。
复杂度分析
每次 BFS 每格最多入队一次，时间 O(mn)，空间 O(mn)。
易错点
逆流时比较方向容易写反：应该是 heights[x][y] >= heights[i][j]（邻格不低于当前）；另外相等高度也能流动。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
def bfs(starts):
seen = set(starts)
queue = list(starts)
head = 0
while head < len(queue):
i, j = queue[head]
head += 1
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < m and 0 <= y < n and (x, y) not in seen and heights[x][y] >= heights[i][j]:
seen.add((x, y))
queue.append((x, y))
return seen
pac = bfs([(i, 0) for i in range(m)] + [(0, j) for j in range(1, n)])
atl = bfs([(i, n - 1) for i in range(m)] + [(m - 1, j) for j in range(n - 1)])
return [[i, j] for i in range(m) for j in range(n) if (i, j) in pac and (i, j) in atl]class Solution {
private int m, n;
private int[][] heights;
private boolean[][] bfs(List<int[]> starts) {
boolean[][] seen = new boolean[m][n];
for (int[] s : starts) seen[s[0]][s[1]] = true;
List<int[]> queue = new ArrayList<>(starts);
int head = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (head < queue.size()) {
int[] c = queue.get(head);
head++;
for (int[] d : dirs) {
int x = c[0] + d[0], y = c[1] + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[c[0]][c[1]]) {
seen[x][y] = true;
queue.add(new int[]{x, y});
}
}
}
return seen;
}
public List<List<Integer>> pacificAtlantic(int[][] heights) {
this.heights = heights;
m = heights.length;
n = heights[0].length;
List<int[]> ps = new ArrayList<>(), as = new ArrayList<>();
for (int i = 0; i < m; i++) ps.add(new int[]{i, 0});
for (int j = 1; j < n; j++) ps.add(new int[]{0, j});
for (int i = 0; i < m; i++) as.add(new int[]{i, n - 1});
for (int j = 0; j < n - 1; j++) as.add(new int[]{m - 1, j});
boolean[][] pac = bfs(ps);
boolean[][] atl = bfs(as);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.add(Arrays.asList(i, j));
return ans;
}
}class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
auto bfs = [&](vector<pair<int, int>> starts) {
vector<vector<bool>> seen(m, vector<bool>(n, false));
for (auto& [i, j] : starts) seen[i][j] = true;
vector<pair<int, int>> queue = starts;
size_t head = 0;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (head < queue.size()) {
auto [i, j] = queue[head];
head++;
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j]) {
seen[x][y] = true;
queue.push_back({x, y});
}
}
}
return seen;
};
vector<pair<int, int>> ps, as;
for (int i = 0; i < m; i++) ps.push_back({i, 0});
for (int j = 1; j < n; j++) ps.push_back({0, j});
for (int i = 0; i < m; i++) as.push_back({i, n - 1});
for (int j = 0; j < n - 1; j++) as.push_back({m - 1, j});
auto pac = bfs(ps);
auto atl = bfs(as);
vector<vector<int>> ans;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.push_back({i, j});
return ans;
}
};func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
bfs := func(starts [][2]int) [][]bool {
seen := make([][]bool, m)
for i := range seen {
seen[i] = make([]bool, n)
}
for _, s := range starts {
seen[s[0]][s[1]] = true
}
queue := append([][2]int{}, starts...)
head := 0
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for head < len(queue) {
c := queue[head]
head++
for _, d := range dirs {
x, y := c[0]+d[0], c[1]+d[1]
if x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[c[0]][c[1]] {
seen[x][y] = true
queue = append(queue, [2]int{x, y})
}
}
}
return seen
}
ps, as := [][2]int{}, [][2]int{}
for i := 0; i < m; i++ {
ps = append(ps, [2]int{i, 0})
as = append(as, [2]int{i, n - 1})
}
for j := 0; j < n; j++ {
if j >= 1 {
ps = append(ps, [2]int{0, j})
}
if j < n-1 {
as = append(as, [2]int{m - 1, j})
}
}
pac := bfs(ps)
atl := bfs(as)
ans := [][]int{}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if pac[i][j] && atl[i][j] {
ans = append(ans, []int{i, j})
}
}
}
return ans
}var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
const bfs = starts => {
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
for (const [i, j] of starts) seen[i][j] = true;
const queue = starts.slice();
let head = 0;
while (head < queue.length) {
const [i, j] = queue[head];
head++;
for (const [x, y] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j]) {
seen[x][y] = true;
queue.push([x, y]);
}
}
}
return seen;
};
const ps = [], as = [];
for (let i = 0; i < m; i++) { ps.push([i, 0]); as.push([i, n - 1]); }
for (let j = 1; j < n; j++) ps.push([0, j]);
for (let j = 0; j < n - 1; j++) as.push([m - 1, j]);
const pac = bfs(ps);
const atl = bfs(as);
const ans = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.push([i, j]);
return ans;
};function pacificAtlantic(heights: number[][]): number[][] {
const m = heights.length, n = heights[0].length;
const bfs = (starts: number[][]): boolean[][] => {
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
for (const [i, j] of starts) seen[i][j] = true;
const queue = starts.slice();
let head = 0;
while (head < queue.length) {
const [i, j] = queue[head];
head++;
for (const [x, y] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j]) {
seen[x][y] = true;
queue.push([x, y]);
}
}
}
return seen;
};
const ps: number[][] = [], as: number[][] = [];
for (let i = 0; i < m; i++) { ps.push([i, 0]); as.push([i, n - 1]); }
for (let j = 1; j < n; j++) ps.push([0, j]);
for (let j = 0; j < n - 1; j++) as.push([m - 1, j]);
const pac = bfs(ps);
const atl = bfs(as);
const ans: number[][] = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.push([i, j]);
return ans;
}其他解法
两种方法都从海洋边界逆流搜索，复杂度相同；BFS 用队列，没有栈溢出风险，DFS 写法更简洁。
解法 2：逆流深度优先搜索 时间 O(m·n)，空间 O(m·n)
从太平洋边界的每个格子出发做 DFS，只走向高度不低于当前格的邻格，标记能到达太平洋的格子。对大西洋边界做同样的 DFS。两组标记都为真的格子就是答案。
代码比 BFS 更短。递归深度最坏为 m·n，网格很大时可能栈溢出，需要改用显式栈。
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
def dfs(seen, i, j):
# 网格可达 4 万格，Python 用显式栈模拟递归，访问顺序与递归一致
seen[i][j] = True
stack = [(i, j)]
while stack:
i, j = stack.pop()
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < m and 0 <= y < n and not seen[x][y] and heights[x][y] >= heights[i][j]:
seen[x][y] = True
stack.append((x, y))
pac = [[False] * n for _ in range(m)]
atl = [[False] * n for _ in range(m)]
for i in range(m):
if not pac[i][0]:
dfs(pac, i, 0)
if not atl[i][n - 1]:
dfs(atl, i, n - 1)
for j in range(n):
if not pac[0][j]:
dfs(pac, 0, j)
if not atl[m - 1][j]:
dfs(atl, m - 1, j)
return [[i, j] for i in range(m) for j in range(n) if pac[i][j] and atl[i][j]]class Solution {
private int m, n;
private int[][] heights;
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private void dfs(boolean[][] seen, int i, int j) {
seen[i][j] = true;
for (int[] d : DIRS) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j])
dfs(seen, x, y);
}
}
public List<List<Integer>> pacificAtlantic(int[][] heights) {
this.heights = heights;
m = heights.length;
n = heights[0].length;
boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
for (int i = 0; i < m; i++) {
if (!pac[i][0]) dfs(pac, i, 0);
if (!atl[i][n - 1]) dfs(atl, i, n - 1);
}
for (int j = 0; j < n; j++) {
if (!pac[0][j]) dfs(pac, 0, j);
if (!atl[m - 1][j]) dfs(atl, m - 1, j);
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.add(Arrays.asList(i, j));
return ans;
}
}class Solution {
public:
int m, n;
vector<vector<int>> h;
void dfs(vector<vector<bool>>& seen, int i, int j) {
seen[i][j] = true;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && h[x][y] >= h[i][j])
dfs(seen, x, y);
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
h = heights;
m = heights.size(); n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n, false)), atl(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
if (!pac[i][0]) dfs(pac, i, 0);
if (!atl[i][n - 1]) dfs(atl, i, n - 1);
}
for (int j = 0; j < n; j++) {
if (!pac[0][j]) dfs(pac, 0, j);
if (!atl[m - 1][j]) dfs(atl, m - 1, j);
}
vector<vector<int>> ans;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.push_back({i, j});
return ans;
}
};func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dfs func(seen [][]bool, i, j int)
dfs = func(seen [][]bool, i, j int) {
seen[i][j] = true
for _, d := range dirs {
x, y := i+d[0], j+d[1]
if x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j] {
dfs(seen, x, y)
}
}
}
grid := func() [][]bool {
g := make([][]bool, m)
for i := range g {
g[i] = make([]bool, n)
}
return g
}
pac, atl := grid(), grid()
for i := 0; i < m; i++ {
if !pac[i][0] {
dfs(pac, i, 0)
}
if !atl[i][n-1] {
dfs(atl, i, n-1)
}
}
for j := 0; j < n; j++ {
if !pac[0][j] {
dfs(pac, 0, j)
}
if !atl[m-1][j] {
dfs(atl, m-1, j)
}
}
ans := [][]int{}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if pac[i][j] && atl[i][j] {
ans = append(ans, []int{i, j})
}
}
}
return ans
}var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
const dfs = (seen, i, j) => {
seen[i][j] = true;
for (const [x, y] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j])
dfs(seen, x, y);
}
};
const pac = Array.from({ length: m }, () => new Array(n).fill(false));
const atl = Array.from({ length: m }, () => new Array(n).fill(false));
for (let i = 0; i < m; i++) {
if (!pac[i][0]) dfs(pac, i, 0);
if (!atl[i][n - 1]) dfs(atl, i, n - 1);
}
for (let j = 0; j < n; j++) {
if (!pac[0][j]) dfs(pac, 0, j);
if (!atl[m - 1][j]) dfs(atl, m - 1, j);
}
const ans = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.push([i, j]);
return ans;
};function pacificAtlantic(heights: number[][]): number[][] {
const m = heights.length, n = heights[0].length;
const dfs = (seen: boolean[][], i: number, j: number): void => {
seen[i][j] = true;
for (const [x, y] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] && heights[x][y] >= heights[i][j])
dfs(seen, x, y);
}
};
const pac: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
const atl: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
for (let i = 0; i < m; i++) {
if (!pac[i][0]) dfs(pac, i, 0);
if (!atl[i][n - 1]) dfs(atl, i, n - 1);
}
for (let j = 0; j < n; j++) {
if (!pac[0][j]) dfs(pac, 0, j);
if (!atl[m - 1][j]) dfs(atl, m - 1, j);
}
const ans: number[][] = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (pac[i][j] && atl[i][j]) ans.push([i, j]);
return ans;
}