LeetCode 417. 太平洋大西洋水流问题

Categories:

题目描述
思路分析
1. 解法一：反向 DFS（推荐）
相似题目

题目描述

✅ 417. 太平洋大西洋水流问题

思路分析

解法一：反向 DFS（推荐）

核心思路：

从太平洋和大西洋边界分别反向 DFS，寻找可流入边界的点。

反向 DFS 只能从低到高或等高移动。

两个访问集合的交集即为答案。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示矩阵尺寸。

空间复杂度：O(m * n)，用于访问标记与递归栈。

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int m;
    private int n;
    private int[][] heights;
    private final int[] dr = {1, -1, 0, 0};
    private final int[] dc = {0, 0, 1, -1};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;

        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacific);
            dfs(i, n - 1, atlantic);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacific);
            dfs(m - 1, j, atlantic);
        }

        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]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    res.add(cell);
                }
            }
        }

        return res;
    }

    private void dfs(int r, int c, boolean[][] ocean) {
        if (ocean[r][c]) {
            return;
        }
        ocean[r][c] = true;

        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                continue;
            }
            if (heights[nr][nc] < heights[r][c]) {
                continue;
            }
            dfs(nr, nc, ocean);
        }
    }
}

func pacificAtlantic(heights [][]int) [][]int {
	m, n := len(heights), len(heights[0])
	pacific := make([][]bool, m)
	atlantic := make([][]bool, m)
	for i := 0; i < m; i++ {
		pacific[i] = make([]bool, n)
		atlantic[i] = make([]bool, n)
	}

	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	var dfs func(r, c int, ocean [][]bool)
	dfs = func(r, c int, ocean [][]bool) {
		if ocean[r][c] {
			return
		}
		ocean[r][c] = true
		for _, d := range dirs {
			nr, nc := r+d[0], c+d[1]
			if nr < 0 || nr >= m || nc < 0 || nc >= n {
				continue
			}
			if heights[nr][nc] < heights[r][c] {
				continue
			}
			dfs(nr, nc, ocean)
		}
	}

	for i := 0; i < m; i++ {
		dfs(i, 0, pacific)
		dfs(i, n-1, atlantic)
	}
	for j := 0; j < n; j++ {
		dfs(0, j, pacific)
		dfs(m-1, j, atlantic)
	}

	res := make([][]int, 0)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if pacific[i][j] && atlantic[i][j] {
				res = append(res, []int{i, j})
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS
130. 被围绕的区域	中等	DFS
329. 矩阵中的最长递增路径	困难	DFS
934. 最短的桥	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/28103603