掘金 后端 ( ) • 2024-06-01 15:01

这道题做出来了,但是时间有点长,以下是AC代码;

import java.util.*;

class Solution {
    int m, n; // m和n分别表示矩阵的行数和列数
    int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0}; // 表示上下左右四个方向
    List<List<Integer>> ans; // 用于存储结果的列表
    int[][] height; // 保存高度矩阵
    class pair {
        int x, y;
        public pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // 主函数,用于找到可以流向太平洋和大西洋的所有点
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        n = heights.length; // 获取行数
        m = heights[0].length; // 获取列数
        ans = new ArrayList<>();
        if (n * m == 1) {
            ans.add(Arrays.asList(0, 0)); // 如果矩阵只有一个元素,则直接返回该点
            return ans;
        }
        height = heights; // 初始化高度矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(i, j, false, false); // 对每个点进行深度优先搜索
            }
        }
        return ans; // 返回结果
    }

    // 深度优先搜索函数
    public void dfs(int x, int y, boolean isPac, boolean isAtl) {
        ArrayDeque<pair> aq = new ArrayDeque<>(); // 用于广度优先搜索的队列
        List<Integer> nowAns = new ArrayList<>(); // 临时存储当前点的结果
        if (x == 0 || y == 0) isPac = true; // 如果当前点在最上行或最左列,则可以流向太平洋
        if (x == n - 1 || y == m - 1) isAtl = true; // 如果当前点在最下行或最右列,则可以流向大西洋
        aq.offer(new pair(x, y)); // 将当前点加入队列
        boolean[][] st = new boolean[n][m]; // 用于标记点是否已访问
        st[x][y] = true;
        while (!aq.isEmpty()) {
            pair p = aq.poll();
            for (int i = 0; i < 4; i++) { // 遍历上下左右四个方向
                int nx = p.x + dx[i], ny = p.y + dy[i];
                if (notLegal(nx, ny)) continue; // 如果新位置不合法,跳过
                if (height[nx][ny] > height[p.x][p.y] || st[nx][ny]) continue; // 如果新位置高度大于当前点或已访问,跳过
                if (nx == 0 || ny == 0) isPac = true; // 如果新位置在最上行或最左列,可以流向太平洋
                if (nx == n - 1 || ny == m - 1) isAtl = true; // 如果新位置在最下行或最右列,可以流向大西洋
                if (isPac && isAtl) { // 如果同时可以流向太平洋和大西洋,加入结果
                    nowAns.add(x);
                    nowAns.add(y);
                    ans.add(nowAns);
                    return;
                }
                aq.offer(new pair(nx, ny)); // 将新位置加入队列
                st[nx][ny] = true; // 标记新位置已访问
            }
        }
        if (isPac && isAtl) { // 如果最后同时可以流向太平洋和大西洋,加入结果
            nowAns.add(x);
            nowAns.add(y);
            ans.add(nowAns);
        }
    }

    // 判断位置是否合法
    public boolean notLegal(int x, int y) {
        return x < 0 || y < 0 || x >= n || y >= m;
    }
}

然后这是用时5ms的做法,很漂亮的dfs

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        int numRows = heights.length;
        int numCols = heights[0].length;
        boolean[][] pacificVisited = new boolean[numRows][numCols];
        boolean[][] atlanticVisited = new boolean[numRows][numCols];
​
        // row by row: pacific floods from left (0), atlantic floods from right (numCols - 1)
        for (int i = 0; i < numRows; i++) {
            dfs(heights, pacificVisited, Integer.MIN_VALUE, i, 0);
            dfs(heights, atlanticVisited, Integer.MIN_VALUE, i, numCols - 1);
        }
​
        // col by col: pacific floods from top (0), floods starts from bottom (numRows - 1)
        for (int j = 0; j < numCols; j++) {
            dfs(heights, pacificVisited, Integer.MIN_VALUE, 0, j);
            dfs(heights, atlanticVisited, Integer.MIN_VALUE, numRows - 1, j);
        }
​
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (pacificVisited[i][j] && atlanticVisited[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }
        return res;
    }
​
    int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public void dfs(int[][] matrix, boolean[][] visited, int height, int x, int y) {
        int m = matrix.length, n = matrix[0].length;
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || matrix[x][y] < height) return;
        visited[x][y] = true;
        for (int[] d : DIRECTIONS) {
            dfs(matrix, visited, matrix[x][y], x + d[0], y + d[1]);
        }
    }
}