leetcode 417. 太平洋大西洋水流问题
题目：417. 太平洋大西洋水流问题
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示:
示例:
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 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]] (上图中带括号的单元).
方法：DFS（深度优先搜索）
思路：DFS（深度优先搜索），通过DFS用两个数组reachPacific、reachAtlantic分别标记所有能够到达太平洋和大西洋的位置（搜索从边界开始）,再遍及每个位置，如果同时被reachPacific和reachAtlantic标记，则说明该位置既可以到达太平洋也可以到达大西洋。
运行数据：执行用时：5 ms，内存消耗：41.1 MB
复杂度分析：
- 时间复杂度：O(max(m,n) * m * n)，其中 m 和 n 分别为矩阵的行数和列数。深度优先搜索的时间复杂度为O(max(m,n) * m * n)，最后的遍历的时间复杂度为O(m * n)。
- 空间复杂度：O(m * n)，其中 m 和 n 分别为矩阵的行数和列数。深度优先搜索的栈开销为O(m * n), 标记数组的开销也为O(m * n)。
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
53
54
55
56
57
58
59
60
61
62
|
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (matrix == null || matrix.length == 0) {
return result;
}
int m = matrix.length;
int n = matrix[0].length;
boolean[][] reachPacific = new boolean[m][n];
boolean[][] reachAtlantic = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(matrix, i, 0, reachPacific);
dfs(matrix, i, n - 1, reachAtlantic);
}
for (int i = 0; i < n; i++) {
dfs(matrix, 0, i, reachPacific);
dfs(matrix, m - 1, i, reachAtlantic);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (reachPacific[i][j] && reachAtlantic[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private void dfs(int[][] matrix, int a, int b, boolean[][] reach) {
if (reach[a][b]) {
return;
}
reach[a][b] = true;
for (int[] d : direction) {
int nextA = d[0] + a;
int nextB = d[1] + b;
if (nextA < 0 || nextA >= matrix.length || nextB < 0 || nextB >= matrix[0].length
|| matrix[a][b] > matrix[nextA][nextB]) {
continue;
}
dfs(matrix, nextA, nextB, reach);
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
