「每日LeetCode」2022年4月27日

本文最后更新于：2023年3月19日 晚上

417.太平洋大西洋水流问题

417.太平洋大西洋水流问题

Category Difficulty Likes Dislikes
algorithms Medium (50.27%) 412 -

Tags
Companies
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” **处于大陆的左边界和上边界，而 **“大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回 网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。

示例 1：
image.png
输入: 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

Discussion | Solution

思路

对每个点 dfs，判断是否已经到了左上边界以及右下边界，是的话将 flag 更新，注意需要提前剪枝，如果 flag 已经都为 true，提前 return。

解答

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
/*
 * @lc app=leetcode.cn id=417 lang=javascript
 *
 * [417] 太平洋大西洋水流问题
 */

// @lc code=start
/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
  const dfs = (i, j, visited, flag) => {
    if (visited.includes(i + "_" + j) || (flag[0] && flag[1])) return;
    if (i === 0 || j === 0) flag[0] = true;
    if (i === heights.length - 1 || j === heights[i].length - 1) flag[1] = true;
    const curHeight = heights[i][j];
    visited.push(i + "_" + j);
    const top = +(heights[i - 1] && heights[i - 1][j]),
      bottom = +(heights[i + 1] && heights[i + 1][j]),
      left = +heights[i][j - 1],
      right = +heights[i][j + 1];
    top <= curHeight && dfs(i - 1, j, visited, flag);
    left <= curHeight && dfs(i, j - 1, visited, flag);
    bottom <= curHeight && dfs(i + 1, j, visited, flag);
    right <= curHeight && dfs(i, j + 1, visited, flag);
  };

  const res = [];

  for (let i = 0; i < heights.length; i++) {
    for (let j = 0; j < heights[i].length; j++) {
      const flag = [false, false];
      dfs(i, j, [], flag);
      if (flag[0] && flag[1]) res.push([i, j]);
    }
  }
  return res;
};
// @lc code=end