【刷题日记】417. 太平洋大西洋水流问题

2023-07-19 54

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本次刷题日记的第 45 篇，力扣题为：417. 太平洋大西洋水流问题，中等

【刷题日记】417. 太平洋大西洋水流问题

本次刷题日记的第 45 篇，力扣题为：417. 太平洋大西洋水流问题 ，中等

一、题目描述：

太平洋，大西洋，做题都做到这里来了，有点意思，一看又是一个数组类型的题目，一起来瞅瞅

二、这道题考察了什么思想？你的思路是什么？

仔细看看本题都给我们说了些什么有用的信息：

题目给出了一个二维数组，每一个格子就是一个岛屿，每个格子上的数字表示岛屿的高度
有水在岛屿上流淌，我们知道水往低处流，那么水只会往周边相邻的比自己矮的岛屿上了走动
题目要求我们找到那些雨水可以流到太平洋，也可以流到到大西洋的岛屿有哪些，需要返回一个岛屿列表

仔细思考一下，我们是不是要模拟一下每一个岛屿是否既可以流到太平洋，又可以流到大西洋，我们遍历题目给出的二维数组，一个格子一个格子的去校验他是否符合要求

一个格子的雨水，可以往四个方向流淌，当流淌到下一个格子的时候，又会有最多向下流淌 4 个方向，如果都符合条件，那么就会一直流下去

看到这里，有没有想到，这个是涉及到深度优先来进行搜索的呢？

如果我们直接遍历题目给出的二维数组，每一个格子都用深度优先来遍历是否符合要求，那么确实会出现大量重复计算的情况，这太暴力了，受不了

那么，我们换一个思维

既然都是要找到某一个岛屿的雨水要流淌到边界上，那么我们正向思维，可能有点胡子眉毛一把抓，直接暴力，但是这个不好，太费劲

那么我们是否可以逆向思维，既然都要流淌到边界，那么我们直接从边界开始搜索，看看从边界进行反流淌，也就是雨水上流，看看流到哪个岛屿是个顶

那在们从 4 个边界分别往内部搜索的时候，满足流水的，我们就可以给格子置位为 true，那么如果某个岛屿既可以流入到左上边界，也可以流入到右下边界，那么这个岛屿就是满足条件的

这个时候，咱们筛选出满足条件的岛屿，放到结果集中即可了

例如图示中，

咱们就拿中间的 5 举个例子，他的其中一条路径就可以从上流入到太平洋，从右流入到大西洋

那么按照这个思路，咱们就可以实现咱们的代码了：

开辟太平洋和大西洋对应的二维数组，主要是用于后续搜索的时候，做标识
从左边界，上边界，右边界，下边界开始搜索，得到太平洋，和大西洋的 2 个二维数组的结果
筛选结果

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，编码的时候需要注意

咱们开辟的空间主要是用来存放该格子是 true 还是 false
true 表示符合条件，可以从边界上流大道当前这一格子，如果是 false，表示不符合条件
最后我们还需要校验当前格子，既可以留到太平洋，也可以留到大西洋，符合该条件的才是我们需要加入到结果集中的

func pacificAtlantic(heights [][]int) [][]int {
    // 定义 四个方向
    direct := []struct{x,y int}{ {-1,0}, {0,-1}, {1,0}, {0,1} }
    // 初始化太平洋的二维数组 ，和大西洋的二维数组
    row := len(heights)
    col := len(heights[0])
    pac , atl := make([][]bool,row), make([][]bool,row)
    for i := range pac {
        pac[i] , atl[i]= make([]bool,col), make([]bool,col)
    }
    var dfs func(x,y int , oce [][]bool )
    dfs = func(x,y int , oce [][]bool ){
        // 说明已经搜索到过
        if oce[x][y] {
            return 
        }
        oce[x][y] = true
        // 如果满足条件就继续搜索
        for _,v := range direct {
            if tx, ty := x+v.x, y+v.y; tx >=0 && ty >=0 && tx<row && ty < col && heights[tx][ty] >= heights[x][y] {
                dfs(tx, ty, oce)
            }
        }
    }
    // 搜索 上面第一行开始
    for i := 0; i < row; i++ {
        dfs(i, 0, pac)
    }
    // 搜索左边第一列开始
    for j := 1; j < col; j++ {
        dfs(0, j, pac)
    }
    // 搜索右边的一列开始
    for i := 0; i < row; i++ {
        dfs(i, col-1, atl)
    }
    // 搜索下面的一行开始
    for j := 0; j < col-1; j++ {
        dfs(row-1, j, atl)
    }
    // 校验太平洋的二维数组 和 大西洋的二维数组，同一个位置都为 true 的坐标有哪些
    res := [][]int{}
    for i,rows := range pac {
        for j,ok := range rows{
            if ok && atl[i][j]{
                res = append(res, []int{i, j})
            }
        } 
    }
    return res
}