LC 827. 最大人工岛

题目描述

这是 LeetCode 上的 827. 最大人工岛 ，难度为困难。

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

并查集 + 枚举

为了方便，我们令 grid 为 g。

根据题意，容易想到通过「并查集」来维护所有连通块大小，再通过「枚举」来找最优翻转点。

具体的，我们可以先使用「并查集」维护所有 $g[i][j] = 1$ 的块连通性，并在维护连通性的过程中，使用 sz[idx] 记录下每个连通块的大小（注意：只有连通块根编号，sz[idx] 才有意义，即只有 sz[find(x)] 才有意义）。

随后我们再次遍历 g，根据原始的 $g[i][j]$ 的值进行分别处理：

若 $g[i][j] = 1$，该位置不会作为翻转点，但真实最大面积未必是由翻转后所导致的（可能取自原有的连通块），因此我们需要将 $sz[root]$ 参与比较，其中 root 为 $(i, j)$ 所属的连通块根节点编号；
若 $g[i][j] = 0$，该位置可作为翻转点，我们可以统计其四联通位置对应的连通块大小总和 tot（注意若四联通方向有相同连通块，只统计一次），那么 $tot + 1$ 即是翻转该位置所得到的新连通块大小。

最后对所有连通块大小取最大值即是答案。

一些细节：为了方便，我们令点 $(i, j)$ 的编号从 $1$ 开始；
同时由于我们本身就要用 sz 数组，因此我们可以随手把并查集的「按秩合并」也加上。体现在 union 操作时，我们总是将小的连通块合并到大的连通块上，从而确保我们并查集单次操作即使在最坏情况下复杂度仍为 $O(\alpha(n))$（可看作常数）。需要注意只有同时应用「路径压缩」和「按秩合并」，并查集操作复杂度才为 $O(\alpha(n))$。

Java 代码：

class Solution {
    static int N = 510;
    static int[] p = new int[N * N], sz = new int[N * N];
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return ;
        if (sz[ra] > sz[rb]) {
            union(b, a);
        } else {
            sz[rb] += sz[ra]; p[ra] = p[rb];
        }
    }
    public int largestIsland(int[][] g) {
        int n = g.length;
        for (int i = 1; i <= n * n; i++) {
            p[i] = i; sz[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 0) continue;
                for (int[] di : dirs) {
                    int x = i + di[0], y = j + di[1];
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                    union(i * n + j + 1, x * n + y + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) {
                    ans = Math.max(ans, sz[find(i * n + j + 1)]);
                } else {
                    int tot = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int[] di : dirs) {
                        int x = i + di[0],y = j + di[1];
                        if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                        int root = find(x * n + y + 1);
                        if (set.contains(root)) continue;
                        tot += sz[root];
                        set.add(root);
                    }
                    ans = Math.max(ans, tot);
                }
            }
        }
        return ans;
    }
}

TypeScript 代码：

const N = 510
const p = new Array<number>(N * N).fill(-1), sz = new Array<number>(N * N).fill(1)
const dirs = [[1,0], [-1,0], [0,1], [0,-1]]
function find(x: number): number {
    if (p[x] != x) p[x] = find(p[x])
    return p[x]
}
function union(a: number, b: number): void {
    const ra = find(a), rb = find(b)
    if (ra == rb) return 
    if (sz[ra] > sz[rb]) {
        union(rb, ra)
    } else {
        sz[rb] += sz[ra]; p[ra] = p[rb]
    }
}
function largestIsland(g: number[][]): number {
    const n = g.length
    for (let i = 1; i <= n * n; i++) {
        p[i] = i; sz[i] = 1
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (g[i][j] == 0) continue
            for (const di of dirs) {
                const x = i + di[0], y = j + di[1]
                if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue
                union(i * n + j + 1, x * n + y + 1)
            }
        }
    }
    let ans = 0
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (g[i][j] == 1) {
                ans = Math.max(ans, sz[find(i * n + j + 1)])
            } else {
                let tot = 1
                const set = new Set()
                for (let di of dirs) {
                    const x = i + di[0], y = j + di[1]
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue
                    const root = find(x * n + y + 1)
                    if (set.has(root)) continue
                    tot += sz[root]
                    set.add(root)
                }
                ans = Math.max(ans, tot)
            }
        }
    }
    return ans
};

Python 代码：

class Solution:
    def find(self, p, x):
        if p[x] != x:
            p[x] = self.find(p, p[x])
        return p[x]

    def union(self, p, sz, a, b):
        ra, rb = self.find(p, a), self.find(p, b)
        if ra == rb:
            return 
        if sz[ra] > sz[rb]:
            ra, rb = rb, ra
        sz[rb] += sz[ra]
        p[ra] = p[rb]

    def largestIsland(self, g: List[List[int]]) -> int:
        n, ans = len(g), 0
        p, sz = [i for i in range(n * n + 10)], [1 for _ in range(n * n + 10)]
        dirs = [[1,0],[-1,0],[0,1],[0,-1]]
        for i in range(n):
            for j in range(n):
                if g[i][j] == 0:
                    continue
                for di in dirs:
                    x, y = i + di[0], j + di[1]
                    if x < 0 or x >= n or y < 0 or y >= n or g[x][y] == 0:
                        continue
                    self.union(p, sz, i * n + j + 1, x * n + y + 1)
        for i in range(n):
            for j in range(n):
                if g[i][j] == 1:
                    ans = max(ans, sz[self.find(p, i * n + j + 1)])
                else:
                    tot = 1
                    vis = set()
                    for di in dirs:
                        x, y = i + di[0], j + di[1]
                        if x < 0 or x >= n or y < 0 or y >= n or g[x][y] == 0:
                            continue
                        root = self.find(p, x * n + y + 1)
                        if root in vis:
                            continue
                        tot += sz[root]
                        vis.add(root)
                    ans = max(ans, tot)
        return ans

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.827 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

并查集枚举

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 1636. 按照频率将数组升序排序上一篇

LC 1624. 两个相同字符之间的最长子字符串下一篇