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

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

/*
 * @lc app=leetcode.cn id=417 lang=typescript
 *
 * [417] 太平洋大西洋水流问题
 */

// @lc code=start
function pacificAtlantic(heights: number[][]): number[][] {}
// @lc code=end

解法 1: BFS

从跟大洋相邻的格子开始 BFS,确定有哪些点能同时到达大西洋和太平洋.

具体做法是将跟太平洋相邻的格子赋值为 1,跟大西洋相邻的格子赋值为 2,之后通过 BFS 将数值传递给比当前更高的格子,表示水能从比当前更高的格子留到当前格子.传递的过程会出现几种情况:

1. 相邻的格子为 0,则说明其还没被访问过,直接将当前格子的数值传递过去,并加入队列中
2. 相邻格子跟当前格子数值相同,既表示已经访问过,则无需处理
3. 相邻格子不为 0,并且跟当前格子数值不同,则其是能同时流向两边的格子,需要将其数值变为 3

实现中可以将几种情况合并,当相邻格子跟当前格子数值不同时,将当前格子数字加给相邻的格子,并加入队列,这样可以同时处理第一种和第三种的情况,并且如果相邻的格子如果已经大于 3 则没必要对其进行处理,这样可以防止两个相邻的格子不断循环相加.最终每个格子最多被处理两次,一次是从 0 到 1 或者 2,一次是从 1 或 2 到大于 3,所以最终时间复杂度是 $O(n*m)$

另外初始化时需要注意,第二次不能直接将边界直接赋值为 2,而是需要加上,这是防止一种特殊的情况,m=1 或者 n=1 的情况,这种情况下没点同时跟两边的大洋相邻,需要将其赋值为 3,我这里的处理是直接将第二次加上 2,这样就不用去特别判断.

BFS 之后,在遍历一次,将格子数值大于等于 3 的坐标点取出返回即可.

function pacificAtlantic(heights: number[][]): number[][] {
  const m = heights.length,
    n = heights[0].length
  // BFS 队列
  const queue: [number, number][] = []
  // 存储每个坐标点的值
  const val: number[][] = Array.from({ length: m }, () => new Array(n).fill(0))
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
        queue.push([i, j])
      }
      if (i === 0 || j === 0) val[i][j] = 1
      if (i === m - 1 || j === n - 1) val[i][j] += 2 // 这里需要加上 2
    }
  }

  const dirs = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ]
  for (let [x, y] of queue) {
    for (let [dx, dy] of dirs) {
      const nx = x + dx,
        ny = y + dy
      if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue // 不处理超出边界的情况
      if (heights[nx][ny] >= heights[x][y] && val[nx][ny] < 3 && val[x][y] !== val[nx][ny]) {
        // 合并处理多种情况
        val[nx][ny] += val[x][y]
        queue.push([nx, ny])
      }
    }
  }

  const res: [number, number][] = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (val[i][j] >= 3) res.push([i, j])
    }
  }
  return res
}

Case

test.each([
  {
    input: {
      heights: [
        [13],
        [4],
        [19],
        [10],
        [1],
        [11],
        [5],
        [17],
        [3],
        [10],
        [1],
        [0],
        [1],
        [4],
        [1],
        [3],
        [6],
        [13],
        [2],
        [16],
        [7],
        [6],
        [3],
        [1],
        [9],
        [9],
        [13],
        [10],
        [9],
        [10],
        [6],
        [2],
        [11],
        [17],
        [13],
        [0],
        [19],
        [7],
        [13],
        [3],
        [9],
        [2],
      ],
    },
    output: [
      [0, 0],
      [1, 0],
      [2, 0],
      [3, 0],
      [4, 0],
      [5, 0],
      [6, 0],
      [7, 0],
      [8, 0],
      [9, 0],
      [10, 0],
      [11, 0],
      [12, 0],
      [13, 0],
      [14, 0],
      [15, 0],
      [16, 0],
      [17, 0],
      [18, 0],
      [19, 0],
      [20, 0],
      [21, 0],
      [22, 0],
      [23, 0],
      [24, 0],
      [25, 0],
      [26, 0],
      [27, 0],
      [28, 0],
      [29, 0],
      [30, 0],
      [31, 0],
      [32, 0],
      [33, 0],
      [34, 0],
      [35, 0],
      [36, 0],
      [37, 0],
      [38, 0],
      [39, 0],
      [40, 0],
      [41, 0],
    ],
  },
  {
    input: {
      heights: [[1]],
    },
    output: [[0, 0]],
  },
  {
    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],
    ],
  },
  {
    input: {
      heights: [
        [2, 1],
        [1, 2],
      ],
    },
    output: [
      [0, 0],
      [0, 1],
      [1, 0],
      [1, 1],
    ],
  },
])('input: heights = $input.heights', ({ input: { heights }, output }) => {
  expect(pacificAtlantic(heights)).toEqual(output)
})