LC.P827[最大人工岛][困难]

题目描述

给你一个大小为 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数组，使用并查集将相邻的1归到同一个集合中，并统计每个岛屿的面积，由size数组记录。

再次遍历grid，对于每个0，统计与该点相邻的四个点所在的岛屿，累加去重后的岛屿面积，更新最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    private int[] p;
    private int[] size;
    private final int[] dirs = new int[]{-1, 0, 1, 0, -1};
    private int n;

    private int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (size[px] > size[py]) {
            size[px] += size[py];
            p[py] = p[px];
        } else {
            size[py] += size[px];
            p[px] = p[py];
        }
    }

    public int largestIsland(int[][] grid) {
        n = grid.length;
        p = new int[n * n];
        size = new int[n * n];
        for (int i = 0; i < n * n; ++i) {
            p[i] = i;
            size[i] = 1;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
                        union(getIndex(i, j), getIndex(x, y));
                    }
                }
            }
        }
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) ans = Math.max(ans, size[find(getIndex(i, j))]);
                else {
                    int t = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dirs[k], y = j + dirs[k + 1];
                        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
                            int root = find(getIndex(x, y));
                            if (!set.contains(root)) {
                                set.add(root);
                                t += size[root];
                            }
                        }
                    }
                    ans = Math.max(ans, t);
                }
            }
        }
        return ans;
    }

    private int getIndex(int i, int j) {
        return i * n + j;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n²)$

并查集模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int[] p = new int[n];
int[] size = new int[n];
for (int i = 0; i < n; ++i) {
    p[i] = i;
    size[i] = 1;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); // 路径压缩 
    return p[x];
}

void union(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
        return;
    }
    p[pa] = pb;
    size[pb] += size[pa];
}