827. 最大人工岛

🔴   🔖  深度优先搜索 广度优先搜索 并查集 数组 矩阵  🔗 力扣 LeetCode

题目

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largestisland in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]

Output: 3

Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: grid = [[1,1],[1,0]]

Output: 4

Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: grid = [[1,1],[1,1]]

Output: 4

Explanation: Can't change any 0 to 1, only one island with area = 4.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] is either 0 or 1.

题目大意

给你一个大小为 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

解题思路

• 1：标记所有岛屿
  使用 DFS 遍历网格，将每个岛屿赋予唯一编号 islandId(从 2 开始累加)，同时计算其面积并存储到 islandSize 中。

• 2：记录最大初始岛屿面积
  如果没有 0，直接返回所有岛屿的面积最大值。

• 3：模拟改变 0 为 1

  • 遍历网格中所有的 0 位置。
  • 检查该位置周围的相邻岛屿，避免重复计算同一岛屿面积。
  • 将相邻岛屿的面积相加，并计算最大可能的新岛屿面积。

复杂度分析

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

  • 遍历网格标记岛屿：O(n^2)
  • 遍历 0 并计算最大面积：O(n^2)

• 空间复杂度：O(n^2)，主要用于存储岛屿标记和队列。

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function (grid) {
	const n = grid.length;
	const dirc = [
		[1, 0],
		[-1, 0],
		[0, 1],
		[0, -1]
	]; // 方向数组
	let islandId = 2; // 从2开始标记岛屿
	let islandSize = new Map();

	// DFS 标记岛屿并计算面积
	const dfs = (i, j, id) => {
		let queue = [[i, j]];
		let size = 0;
		grid[i][j] = id;

		while (queue.length) {
			let [x, y] = queue.pop();
			size++;
			for (let [dx, dy] of dirc) {
				const nx = x + dx;
				const ny = y + dy;
				if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 1) {
					grid[nx][ny] = id;
					queue.push([nx, ny]);
				}
			}
		}
		return size;
	};

	// 标记所有岛屿并计算初始岛屿面积
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] == 1) {
				islandSize.set(islandId, dfs(i, j, islandId));
				islandId++;
			}
		}
	}

	// 初始化最大岛屿面积
	let maxIsland = Math.max(...islandSize.values(), 0);

	// 遍历每个水域（0），尝试连接相邻岛屿
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] == 0) {
				let seen = new Set();
				let newSize = 1;
				for (let [dx, dy] of dirc) {
					const nx = i + dx;
					const ny = j + dy;
					if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] > 1) {
						let id = grid[nx][ny];
						if (!seen.has(id)) {
							seen.add(id);
							newSize += islandSize.get(id);
						}
					}
				}
				maxIsland = Math.max(maxIsland, newSize);
			}
		}
	}

	return maxIsland;
};