|
5 | 5 |
|
6 | 6 | ## 题目大意
|
7 | 7 |
|
| 8 | +**描述**:给定一个 `m * n` 大小的二维非负整数矩阵 `heights` 来表示一片大陆上各个单元格的高度。`heights[i][j]` 表示第 `i` 行第 `j` 列所代表的陆地高度。这个二维矩阵所代表的陆地被太平洋和大西洋所包围着。左上角是「太平洋」,右下角是「大西洋」。规定水流只能按照上、下、左、右四个方向流动,且只能从高处流到低处,或者在同等高度上流动。 |
8 | 9 |
|
| 10 | +**要求**:找出代表陆地的二维矩阵中,水流既可以从该处流动到太平洋,又可以流动到大西洋的所有坐标。以二维数组 `res` 的形式返回,其中 `res[i] = [ri, ci]` 表示雨水从单元格 `(ri, ci)` 既可流向太平洋也可流向大西洋。 |
9 | 11 |
|
10 |
| -给定一个 `m * n` 大小的二维非负整数矩阵 `heights` 来表示一片大陆上各个单元格的高度。`heights[i][j]` 表示第 `i` 行第 `j` 列所代表的陆地高度。这个二维矩阵所代表的陆地被太平洋和大西洋所包围着。左上角是「太平洋」,右下角是「大西洋」。规定水流只能按照上、下、左、右四个方向流动,且只能从高处流到低处,或者在同等高度上流动。 |
| 12 | +**说明**: |
11 | 13 |
|
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$。 |
13 | 18 |
|
14 |
| -注意:陆地与太平洋、大西洋的关系如下图所示: |
| 19 | +**示例**: |
15 | 20 |
|
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 | + |
| 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]] |
24 | 30 | ```
|
25 | 31 |
|
26 | 32 | ## 解题思路
|
27 | 33 |
|
28 |
| -直接根据矩阵位置判断是否能流向太平洋和大西洋不太容易。我们可以换个思路。分别从太平洋和大西洋(就是矩形边缘)出发,逆流而上,找出水流逆流能达到的地方,可以用两个二维数组 `pacific`、`atlantic` 分别记录太平洋和大西洋能到达的位置。 |
| 34 | +### 思路 1:深度优先搜索 |
| 35 | + |
| 36 | +雨水由高处流向低处,如果我们根据雨水的流向搜索,来判断是否能从某一位置流向太平洋和大西洋不太容易。我们可以换个思路。 |
29 | 37 |
|
30 |
| -然后再对二维数组进行一次遍历,找出两者交集的位置,将其加入答案数组中。 |
| 38 | +1. 分别从太平洋和大西洋(就是矩形边缘)出发,逆流而上,找出水流逆流能达到的地方,可以用两个二维数组 `pacific`、`atlantic` 分别记录太平洋和大西洋能到达的位置。 |
| 39 | +2. 然后再对二维数组进行一次遍历,找出两者交集的位置,就是雨水既可流向太平洋也可流向大西洋的位置,将其加入答案数组 `res` 中。 |
| 40 | +3. 最后返回答案数组 `res`。 |
31 | 41 |
|
32 |
| -## 代码 |
| 42 | +### 思路 1:代码 |
33 | 43 |
|
34 | 44 | ```Python
|
35 | 45 | class Solution:
|
@@ -66,3 +76,7 @@ class Solution:
|
66 | 76 | return res
|
67 | 77 | ```
|
68 | 78 |
|
| 79 | +### 思路 1:复杂度分析 |
| 80 | + |
| 81 | +- **时间复杂度**:$O(m \times n)$。其中 $m$ 和 $n$ 分别为行数和列数。 |
| 82 | +- **空间复杂度**:$O(m \times n)$。 |
0 commit comments