太平洋大西洋水流：从海岸反向搜索

核心结论#

逐个单元格模拟水流会产生大量重复搜索。更直接的方法是从海岸出发，沿着高度不下降的方向反向搜索：分别得到能流向太平洋和大西洋的单元格集合，取交集即可。

搜索方向#

正向水流可以从高处流向等高或更低的位置。反向搜索则只能从当前格走向等高或更高的位置。

• 太平洋边界：第一行和第一列。
• 大西洋边界：最后一行和最后一列。
• 结果：同时被两个搜索访问的坐标。

Java 实现#

class Solution {
    private static final int[][] DIRECTIONS = {
        {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int rows = heights.length;
        int columns = heights[0].length;
        boolean[][] pacific = new boolean[rows][columns];
        boolean[][] atlantic = new boolean[rows][columns];

        for (int column = 0; column < columns; column++) {
            search(heights, 0, column, pacific);
            search(heights, rows - 1, column, atlantic);
        }
        for (int row = 0; row < rows; row++) {
            search(heights, row, 0, pacific);
            search(heights, row, columns - 1, atlantic);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (pacific[row][column] && atlantic[row][column]) {
                    result.add(List.of(row, column));
                }
            }
        }
        return result;
    }

    private void search(
        int[][] heights,
        int row,
        int column,
        boolean[][] reachable
    ) {
        reachable[row][column] = true;
        for (int[] direction : DIRECTIONS) {
            int nextRow = row + direction[0];
            int nextColumn = column + direction[1];
            if (
                nextRow >= 0 && nextRow < heights.length &&
                nextColumn >= 0 && nextColumn < heights[0].length &&
                !reachable[nextRow][nextColumn] &&
                heights[nextRow][nextColumn] >= heights[row][column]
            ) {
                search(heights, nextRow, nextColumn, reachable);
            }
        }
    }
}

正确性与复杂度#

反向搜索访问的恰好是存在一条非递增正向路径通往对应海洋的单元格。两个访问集合的交集因此正好满足同时流向两片海洋的条件。

每个单元格在每次搜索中最多访问一次，时间复杂度为 O(mn)，访问数组与递归栈最坏空间为 O(mn)。

验证#

测试单元素、单行、全等高、严格递增和严格递减矩阵。矩阵很大时可将递归 DFS 改成队列 BFS，避免调用栈过深。

参考#

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