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

大佬，牛！！！

• 题目：就是一个单元格内找到一些点，要求这些点可以通到左边界或者上边界，然后同时还能通到有边界或者下边界。这个通的过程中也是有要求的，每一次都必须往小于等于本节点。例如你要想从i，j到i-1，j则必须要求i-1，j要小于等于i，j。
• 大佬的思路：我们要想遍历每个节点，其实比较复杂，所以我们反其道。就是从左边界以及上边界开始往里面走，走的时候，必须要求大于等于当前的节点才能走。然后再从有边界以及下边界走。然后两个重合的部分就是我们的最终的结果。思路是大佬的，但是代码是自己的，跟大佬的有些不同，我是在进入递归之前，就对这个点是不是可以进行递归进行了判断。
• 技巧：这里就是dfs。但是这里我们遍历过这个点以后，递归的时候不需要对其进行修改，因为这个点只要能到，我们就不用管了。也就是说，递归过程中有一个vis，我们是不需要改回原来的值的。

java代码

class Solution {
    int m = 0, n = 0;

    public List> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        boolean[][] mapLT = new boolean[m][n];// 左上的水
        boolean[][] mapRB = new boolean[m][n];// 右下的水
        for (int i = 0; i < m; i++) {
            if (!mapLT[i][0]) {// 第一列
                mapLT[i][0] = true;
                dfs(heights, mapLT, i, 0);
            }
            if (!mapRB[i][n - 1]) {// 最后一列
                mapRB[i][n - 1] = true;
                dfs(heights, mapRB, i, n - 1);
            }
        }
        for (int i = 0; i < n; i++) {
            if (!mapLT[0][i]) {// 第一行
                mapLT[0][i] = true;
                dfs(heights, mapLT, 0, i);
            }
            if (!mapRB[m - 1][i]) {// 最后一行
                mapRB[m - 1][i] = true;
                dfs(heights, mapRB, m - 1, i);
            }
        }
        List> ansList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mapLT[i][j] && mapRB[i][j]) {
                    ArrayList temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    ansList.add(temp);
                }
            }
        }
        return ansList;
    }


    private void dfs(int[][] heights, boolean[][] vis, int h, int l) {
        // 下一行
        if (h + 1 < m && heights[h + 1][l] >= heights[h][l] && !vis[h + 1][l]) {
            vis[h + 1][l] = true;
            dfs(heights, vis, h + 1, l);
        }
        // 上一行
        if (h - 1 >= 0 && heights[h - 1][l] >= heights[h][l] && !vis[h - 1][l]) {
            vis[h - 1][l] = true;
            dfs(heights, vis, h - 1, l);
        }
        // 下一列
        if (l + 1 < n && heights[h][l + 1] >= heights[h][l] && !vis[h][l + 1]) {
            vis[h][l + 1] = true;
            dfs(heights, vis, h, l + 1);
        }
        // 上一列
        if (l - 1 >= 0 && heights[h][l - 1] >= heights[h][l] && !vis[h][l - 1]) {
            vis[h][l - 1] = true;
            dfs(heights, vis, h, l - 1);
        }
    }
}

• 总结：题目还是比较有意思的，在递归函数中写的比较冗长了，其实可以定义一个数字，分别表示往四个方向走，然后对四个方向都进行越界的判断，但是空间复杂度有点高。