【刷题日记】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 }
按照这样的编码，虽然编码比之前的题好像要多一点，但是实际上理解起来也是非常容易的，主要是我们需要考虑到反向搜索，而不是一味的暴力求解
四、总结：
根据这样的编码方式，时间复杂度会是多少呢？仔细查看和时间的 xdm 应该是看的出来的，这里的代码接口，中间涉及到的时间复杂度可以参考咱们在最后遍历二维数组的位置，从此处就可以看出来，咱们的时间复杂度是 O(mn) ，m 和 n 分别是海洋的行和列的值
当然，空间复杂度也是 O(mn) ，因为，咱们开辟了一个二维数组，行和列都是和题目给出的数组是一样的，因此占用了 O(mn) 级别的空间消耗
原题地址：868. 二进制间距
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
