困难

问题描述

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格 0 变成 1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格 0 变成 1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有 0 可以让我们变成 1，面积依然为 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 为 0 或 1

标记 + 枚举

创建一个与原始矩阵大小相同的矩阵记录各个区域所属的岛屿，对不同的岛屿进行标记，由于 $i * n + j$ 能够唯一确定某个位置，因此可以用这个公式计算出的值对一片岛屿进行标记。查找一整片岛屿的过程可以使用深度优先搜索或广度优先搜索。同时，若遍历过程中遇到非岛屿的区域，记录其位置，用于后续枚举。处理完毕后，若非岛屿区域数组为空，则说明整片区域连通，岛屿面积为 $n \times n$，否则，枚举非岛屿区域，计算将其置为岛屿后连通区域大小，返回最大值即可。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function (grid) {
  const n = grid.length
  const map = new Map()
  const tag = new Array(n).fill(0).map(() => new Array(n).fill(-1))
  const dirs = [
    [0, -1],
    [0, 1],
    [-1, 0],
    [1, 0]
  ]
  const dfs = (x, y, num) => {
    let area = 1
    tag[x][y] = num
    for (const dir of dirs) {
      const nx = x + dir[0]
      const ny = y + dir[1]
      if (0 <= nx && nx < n && 0 <= ny && ny < n && grid[nx][ny] === 1 && tag[nx][ny] === -1) {
        area += dfs(nx, ny, num)
      }
    }
    return area
  }
  const list = []
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const num = i * n + j
      if (grid[i][j] === 1 && tag[i][j] === -1) {
        map.set(num, dfs(i, j, num))
      } else if (grid[i][j] === 0) {
        list.push(num)
      }
    }
  }
  if (list.length === 0) return n * n
  let ans = 0
  for (const pos of list) {
    const connected = new Set()
    const x = ~~(pos / n)
    const y = pos % n
    let area = 1
    for (const dir of dirs) {
      const nx = x + dir[0]
      const ny = y + dir[1]
      if (0 <= nx && nx < n && 0 <= ny && ny < n && tag[nx][ny] !== -1 && !connected.has(tag[nx][ny])) {
        connected.add(tag[nx][ny])
        area += map.get(tag[nx][ny])
      }
    }
    ans = Math.max(ans, area)
  }
  return ans
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$