友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
417. 太平洋大西洋水流问题
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
示例 1：
输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：
输入: heights = [[2,1],[1,2]] 输出: [[0,0],[0,1],[1,0],[1,1]]
提示：
-
m == heights.length -
n == heights[r].length -
1 <= m, n <= 200 -
0 <= heights[r][c] <= 105
思路分析
先搞清楚题目。题目要求是找出水既可以流向太平洋，又可以流向大西洋的坐标点集合。水往低处流，靠近海洋的坐标点，都是可以流向海洋的点，靠着太平洋，就流向太平洋；靠着大西洋，就流向大西洋。以这些点为起点，深度优先遍历或者广度优先遍历，找出“步步高升”的点。
搞清楚题目要求，就是一个 DFS 或 BFS：分别以靠着海洋的点为起点，找出“步步高升”的点，最后求两个海洋的高点交集。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-06 22:54:09
*/
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
for (int i = 0; i < n; i++) {
dfs(heights, pacific, 0, i);
dfs(heights, atlantic, m - 1, n - i - 1);
}
for (int i = 0; i < m; i++) {
dfs(heights, pacific, i, 0);
dfs(heights, atlantic, m - 1 - i, n - 1);
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(List.of(i, j));
}
}
}
return result;
}
private void dfs(int[][] heights, boolean[][] fic, int row, int column) {
if (row < 0 || row >= heights.length || column < 0 || column >= heights[0].length) {
return;
}
if (fic[row][column]) {
return;
}
fic[row][column] = true;
// 上
if (row - 1 >= 0 && heights[row][column] <= heights[row - 1][column]) {
dfs(heights, fic, row - 1, column);
}
// 下
if (row + 1 < heights.length && heights[row][column] <= heights[row + 1][column]) {
dfs(heights, fic, row + 1, column);
}
// 左
if (column - 1 >= 0 && heights[row][column - 1] >= heights[row][column]) {
dfs(heights, fic, row, column - 1);
}
// 右
if (column + 1 < heights[0].length && heights[row][column] <= heights[row][column + 1]) {
dfs(heights, fic, row, column + 1);
}
}