LeetCode 题解工作台
最大人工岛
给你一个大小为 n x n 二进制矩阵 grid 。 最多 只能将一格 0 变成 1 。 返回执行此操作后， grid 中最大的岛屿面积是多少？ 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 示例 1: 输入: grid = [[1, 0], [0, 1]] 输出: 3 解释: 将一格0变成…
5
题型
6
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
我们可以给每个连通块一个唯一的标识，用数组 记录每个位置所属的连通块，即 表示 $(i, j)$ 所属的连通块编号。用数组 记录每个连通块的大小，即 表示连通块 的大小。 首先，我们遍历整个矩阵，对于每个 $grid[i][j] = 1$ 且 $p[i][j] = 0$ 的位置，我们对其进行深度优先搜索，将其所属的连通块标记为 ，并统计连通块的大小。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 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.lengthn == grid[i].length1 <= n <= 500grid[i][j]为0或1
解题思路
方法一：DFS
我们可以给每个连通块一个唯一的标识，用数组 记录每个位置所属的连通块，即 表示 所属的连通块编号。用数组 记录每个连通块的大小，即 表示连通块 的大小。
首先，我们遍历整个矩阵，对于每个 且 的位置，我们对其进行深度优先搜索，将其所属的连通块标记为 ，并统计连通块的大小。
接着，我们遍历整个矩阵，对于每个 的位置，我们找到其上、下、左、右四个位置所属的连通块，将这些连通块的大小相加，再加上当前位置的 ，即可得到将当前位置变为 后的最大岛屿面积。
时间复杂度 ，空间复杂度 。其中 为矩阵的边长。
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int):
p[i][j] = root
cnt[root] += 1
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] and p[x][y] == 0:
dfs(x, y)
n = len(grid)
cnt = Counter()
p = [[0] * n for _ in range(n)]
dirs = (-1, 0, 1, 0, -1)
root = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x and p[i][j] == 0:
root += 1
dfs(i, j)
ans = max(cnt.values() or [0])
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 0:
s = set()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n:
s.add(p[x][y])
ans = max(ans, sum(cnt[root] for root in s) + 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \times m) |
| 空间 | O(n \times m) |
面试官常问的追问
外企场景- question_mark
Checking DFS versus BFS trade-offs is important for large grids.
- question_mark
Remember to handle grids fully filled with 1s where no flips are needed.
- question_mark
Be ready to explain how using a map for island sizes avoids repeated recalculations.
常见陷阱
外企场景- error
Counting the same island twice when multiple zeros share neighbors.
- error
Not labeling islands correctly, leading to incorrect size computation.
- error
Forgetting the edge case where no zeros exist, requiring total grid count.
进阶变体
外企场景- arrow_right_alt
Allow flipping multiple zeros and find maximum combined island size.
- arrow_right_alt
Use Union-Find instead of DFS to track connected components dynamically.
- arrow_right_alt
Compute largest island size when diagonal connections are also considered.