Skip to content

Commit 66a2aec

Browse files
committed
Update 0417. 太平洋大西洋水流问题.md
1 parent 619405b commit 66a2aec

File tree

1 file changed

+28
-14
lines changed

1 file changed

+28
-14
lines changed

Solutions/0417. 太平洋大西洋水流问题.md

Lines changed: 28 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -5,31 +5,41 @@
55

66
## 题目大意
77

8+
**描述**:给定一个 `m * n` 大小的二维非负整数矩阵 `heights` 来表示一片大陆上各个单元格的高度。`heights[i][j]` 表示第 `i` 行第 `j` 列所代表的陆地高度。这个二维矩阵所代表的陆地被太平洋和大西洋所包围着。左上角是「太平洋」,右下角是「大西洋」。规定水流只能按照上、下、左、右四个方向流动,且只能从高处流到低处,或者在同等高度上流动。
89

10+
**要求**:找出代表陆地的二维矩阵中,水流既可以从该处流动到太平洋,又可以流动到大西洋的所有坐标。以二维数组 `res` 的形式返回,其中 `res[i] = [ri, ci]` 表示雨水从单元格 `(ri, ci)` 既可流向太平洋也可流向大西洋。
911

10-
给定一个 `m * n` 大小的二维非负整数矩阵 `heights` 来表示一片大陆上各个单元格的高度。`heights[i][j]` 表示第 `i` 行第 `j` 列所代表的陆地高度。这个二维矩阵所代表的陆地被太平洋和大西洋所包围着。左上角是「太平洋」,右下角是「大西洋」。规定水流只能按照上、下、左、右四个方向流动,且只能从高处流到低处,或者在同等高度上流动。
12+
**说明**
1113

12-
要求:找出代表陆地的二维矩阵中,水流既可以从该处流动到太平洋,又可以流动到大西洋的所有坐标。
14+
- $m == heights.length$。
15+
- $n == heights[r].length$。
16+
- $1 \le m, n \le 200$。
17+
- $0 \le heights[r][c] \le 10^5$。
1318

14-
注意:陆地与太平洋、大西洋的关系如下图所示
19+
**示例**
1520

16-
```
17-
太平洋 ~ ~ ~ ~ ~ ~
18-
~ 1 2 2 3 (5) *
19-
~ 3 2 3 (4) (4) *
20-
~ 2 4 (5) 3 1 *
21-
~ (6) (7) 1 4 5 *
22-
~ (5) 1 1 2 4 *
23-
* * * * * 大西洋
21+
![](https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg)
22+
23+
```Python
24+
输入: 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]]
25+
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
26+
27+
28+
输入: heights = [[2,1],[1,2]]
29+
输出: [[0,0],[0,1],[1,0],[1,1]]
2430
```
2531

2632
## 解题思路
2733

28-
直接根据矩阵位置判断是否能流向太平洋和大西洋不太容易。我们可以换个思路。分别从太平洋和大西洋(就是矩形边缘)出发,逆流而上,找出水流逆流能达到的地方,可以用两个二维数组 `pacific``atlantic` 分别记录太平洋和大西洋能到达的位置。
34+
### 思路 1:深度优先搜索
35+
36+
雨水由高处流向低处,如果我们根据雨水的流向搜索,来判断是否能从某一位置流向太平洋和大西洋不太容易。我们可以换个思路。
2937

30-
然后再对二维数组进行一次遍历,找出两者交集的位置,将其加入答案数组中。
38+
1. 分别从太平洋和大西洋(就是矩形边缘)出发,逆流而上,找出水流逆流能达到的地方,可以用两个二维数组 `pacific``atlantic` 分别记录太平洋和大西洋能到达的位置。
39+
2. 然后再对二维数组进行一次遍历,找出两者交集的位置,就是雨水既可流向太平洋也可流向大西洋的位置,将其加入答案数组 `res` 中。
40+
3. 最后返回答案数组 `res`
3141

32-
## 代码
42+
### 思路 1:代码
3343

3444
```Python
3545
class Solution:
@@ -66,3 +76,7 @@ class Solution:
6676
return res
6777
```
6878

79+
### 思路 1:复杂度分析
80+
81+
- **时间复杂度**:$O(m \times n)$。其中 $m$ 和 $n$ 分别为行数和列数。
82+
- **空间复杂度**:$O(m \times n)$。

0 commit comments

Comments
 (0)