在问 · 算法题解

827. 最大人工岛

困难图论岛屿标号 + 枚举填海力扣原题 ↗
在线写代码并运行看动画推演问 AI 讲解

题目描述

输入 n x n 的二进制矩阵 grid，1 是陆地，0 是海水。沿上下左右四个方向连在一起的陆地构成一个岛屿，岛屿面积是其中 1 的个数。

你最多可以把一个 0 改成 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 可改，整个矩阵就是一个面积为 4 的岛。

数据范围

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

解题思路：岛屿标号 + 枚举填海

分两遍。第一遍给每个岛编号（从 2 开始，以免与 0、1 冲突），用 DFS 把整个岛的格子都改成编号，同时记录 area[编号] = 面积。第二遍枚举每个 0，看它上下左右分别属于哪些岛，编号去重后把这些岛的面积加起来再加 1（它自己）。所有候选与原本最大的岛取最大值。

为什么正确

第一遍结束后，grid 中每个陆地格子的值都是它所属岛的编号，area 记录每个编号对应的岛面积。

复杂度分析

时间 O(n²)：每个格子在第一遍被访问常数次，第二遍每个 0 只看 4 个邻居。空间 O(n²)。

易错点

同一个岛可能从 0 的两个方向相邻，必须按编号去重，不能重复加面积。另外全是 1 的矩阵没有 0 可改，答案就是 n²，best 要用原有最大岛初始化。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        area = {}
        label = 2
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    grid[r][c] = label
                    stack = [(r, c)]
                    size = 0
                    while stack:
                        x, y = stack.pop()
                        size += 1
                        for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                                grid[nx][ny] = label
                                stack.append((nx, ny))
                    area[label] = size
                    label += 1
        best = max(area.values(), default=0)
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    ids = set()
                    for nx, ny in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] > 1:
                            ids.add(grid[nx][ny])
                    best = max(best, 1 + sum(area[i] for i in ids))
        return best

载入编辑器，自己跑一遍 →

其他解法

搜索标号直观、常数小；并查集把连通块维护交给通用数据结构，支持增量合并。两者的第二遍枚举完全相同。

解法 2：并查集 时间 O(n²·α(n²))，空间 O(n²)

把格子 (r, c) 编号为 r·n + c。第一遍把所有相邻的陆地格子合并，按大小合并并在根上记录连通块面积。第二遍枚举每个海洋格子，取四个邻居中陆地格子的根并去重，把这些根的面积加起来再加 1，取最大值。全是陆地时答案是 n²。

不需要显式搜索，也不修改 grid，并查集的根本身就是岛屿编号。代码比搜索标号稍长，常数也略大，但在格子动态变成陆地的变体题中更通用。

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        parent = list(range(n * n))
        size = [1] * (n * n)

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra == rb:
                return
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    if r + 1 < n and grid[r + 1][c] == 1:
                        union(r * n + c, (r + 1) * n + c)
                    if c + 1 < n and grid[r][c + 1] == 1:
                        union(r * n + c, r * n + c + 1)
        best = 0
        has_water = False
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    best = max(best, size[find(r * n + c)])
                    continue
                has_water = True
                roots = set()
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                        roots.add(find(nr * n + nc))
                best = max(best, 1 + sum(size[x] for x in roots))
        return best if has_water else n * n

图论 专题的其他题目

查看 图论 全部题目 →