417. 太平洋大西洋水流问题
417. 太平洋大西洋水流问题
🟠 🔖 深度优先搜索 广度优先搜索 数组 矩阵 🔗 力扣 LeetCode
题目
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return _a 2D list of grid coordinates _result whereresult[i] = [ri, ci]denotes that rain water can flow from cell(ri, ci)toboth the Pacific and Atlantic oceans.
Example 1:
Input: 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]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic OceanNote that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
题目大意
有一个 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.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
解题思路
- 创建两个访问矩阵
pacific和atlantic，用于标记是否能到达对应的海洋。 - 从边界出发进行深度优先搜索（DFS）：
- 太平洋：从第一列（左侧）和第一行（顶部）出发，标记所有可以到达太平洋的点。
- 大西洋：从最后一列（右侧）和最后一行（底部）出发，标记所有可以到达大西洋的点。
- 遍历整个矩阵，同时能到达太平洋和大西洋的点即为答案。
复杂度分析
- 时间复杂度：
O(m * n)，每个点最多访问一次。 - 空间复杂度：
O(m * n)，存储pacific和atlantic两个m * n访问矩阵。
代码
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function (heights) {
const m = heights.length;
const n = heights[0].length;
// 访问矩阵
let pacific = new Array(m).fill().map(() => new Array(n).fill(false));
let atlantic = new Array(m).fill().map(() => new Array(n).fill(false));
// 深度优先搜索 (DFS)
const dfs = (i, j, ocean) => {
ocean[i][j] = true; // 标记为可达
const directions = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1]
]; // 四个方向
for (let [di, dj] of directions) {
let ni = i + di,
nj = j + dj;
if (
ni >= 0 &&
ni < m &&
nj >= 0 &&
nj < n && // 不越界
!ocean[ni][nj] && // 该点未访问过
heights[ni][nj] >= heights[i][j] // 确保水流方向是从高到低或相等
) {
dfs(ni, nj, ocean);
}
}
};
// 从边界开始搜索
for (let i = 0; i < m; i++) {
dfs(i, 0, pacific); // 左侧流向太平洋
dfs(i, n - 1, atlantic); // 右侧流向大西洋
}
for (let j = 0; j < n; j++) {
dfs(0, j, pacific); // 上方流向太平洋
dfs(m - 1, j, atlantic); // 下方流向大西洋
}
// 收集结果
let res = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
res.push([i, j]);
}
}
}
return res;
};