LeetCode 417. 太平洋大西洋水流问题解题思路核心思路反向 DFS/BFS正向思路是枚举每个格子判断它能否流向两个大洋但这样每个格子都要搜索一次复杂度高。反向思考从海洋边界出发逆流而上。水只能从高往低或等高处流所以反向遍历时下一个格子必须 height 当前格子。· 太平洋左边界j0 上边界i0· 大西洋右边界jn-1 下边界im-1分别从两片大洋的边界出发做 DFS/BFS标记能到达的格子。最后 两片大洋都能到达 的格子就是答案。代码实现DFS推荐classSolution{privateintm,n;privateint[][]heights;privateint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};publicListListIntegerpacificAtlantic(int[][]heights){this.heightsheights;this.mheights.length;this.nheights[0].length;boolean[][]pacificnewboolean[m][n];boolean[][]atlanticnewboolean[m][n];// 太平洋左边界 上边界for(inti0;im;i)dfs(i,0,pacific);for(intj0;jn;j)dfs(0,j,pacific);// 大西洋右边界 下边界for(inti0;im;i)dfs(i,n-1,atlantic);for(intj0;jn;j)dfs(m-1,j,atlantic);// 收集交集ListListIntegerresnewArrayList();for(inti0;im;i){for(intj0;jn;j){if(pacific[i][j]atlantic[i][j]){res.add(Arrays.asList(i,j));}}}returnres;}privatevoiddfs(inti,intj,boolean[][]visited){if(visited[i][j])return;visited[i][j]true;for(int[]d:dirs){intniid[0],njjd[1];// 反向逆流下一个格子必须 当前格子if(ni0nimnj0njn!visited[ni][nj]heights[ni][nj]heights[i][j]){dfs(ni,nj,visited);}}}}代码实现BFS如果担心递归深度导致栈溢出极端情况下 m*n 很大可用 BFSclassSolution{privateint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};publicListListIntegerpacificAtlantic(int[][]heights){intmheights.length,nheights[0].length;boolean[][]pacificnewboolean[m][n];boolean[][]atlanticnewboolean[m][n];// 把两片海洋的所有边界点加入队列for(inti0;im;i){bfs(heights,i,0,pacific);bfs(heights,i,n-1,atlantic);}for(intj0;jn;j){bfs(heights,0,j,pacific);bfs(heights,m-1,j,atlantic);}ListListIntegerresnewArrayList();for(inti0;im;i){for(intj0;jn;j){if(pacific[i][j]atlantic[i][j]){res.add(Arrays.asList(i,j));}}}returnres;}privatevoidbfs(int[][]heights,intsi,intsj,boolean[][]visited){intmheights.length,nheights[0].length;if(visited[si][sj])return;Queueint[]queuenewArrayDeque();queue.offer(newint[]{si,sj});visited[si][sj]true;while(!queue.isEmpty()){int[]curqueue.poll();for(int[]d:dirs){intnicur[0]d[0],njcur[1]d[1];if(ni0nimnj0njn!visited[ni][nj]heights[ni][nj]heights[cur[0]][cur[1]]){visited[ni][nj]true;queue.offer(newint[]{ni,nj});}}}}}关键点说明反向遍历条件正向是从高到低流反向就从低到高走所以判断条件是 heights[ni][nj] heights[i][j]。等号很重要水可以在等高处流动。每个海洋的边界点左边界 (i, 0)、上边界 (0, j) 属于太平洋右边界 (i, n-1)、下边界 (m-1, j) 属于大西洋。四个角落会同时属于两片大洋比如 (0,0) 既在左边界又在边界是太平洋(0,n-1) 等是两片交叉点需分别处理代码中分别调用 dfs/bfsvisited 数组各自独立因此角落会被正确标记。每个格子最多被访问一次两遍遍历共 O(mn)。复杂度分析· 时间复杂度O(m × n) —— 每个格子最多被 DFS/BFS 访问常数次· 空间复杂度O(m × n) —— visited 数组 递归栈/队列对比正向暴力为何会超时正向对每个格子做一次搜索最坏是 O((mn)²)在 200×200 数据下会 TLE。反向从边界出发 是本题的关键突破口也是图论中从结果反推的经典技巧。延伸· LeetCode 130. 被围绕的区域同样从边界出发反向标记题目思路高度相似· LeetCode 1020. 飞地的数量从边界出发标记能到达陆地的变体