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

主要思路 并查集
将同一个岛屿的点加入并查集中，并且计算当前并查集的岛屿大小
然后再次遍历，更新 ans 中最大岛屿的面积。
遇到需要填海的 ·海· 从四个方向看有没有可联通的岛屿，将四个方向的岛屿面积，连同填海的面积 1 求和后更新 ans 中的最大面积

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
func largestIsland(grid [][]int) int {
	n := len(grid)
	ans := 0
	// dfs 遍历的时候会超界
	p, sz := make([]int, n*n + 1), make([]int, n*n + 1)
	for i:=0; i<n*n; i++ {
		p[i] = i // 并查集初始化
		sz[i] = 1 // 每个格子所占的面积
	}
	dir := [][]int{
		[]int{-1, 0}, []int{1, 0}, []int{0, -1}, []int{0, 1},
	}
	for i:=0; i<n; i++ {
		for j:=0; j<n; j++ {
		// 不合规
		if grid[i][j] == 0 {
			continue
		}
		for _, d := range dir {
			x, y := i + d[0], j + d[1]
			// 超界 or 下一个方向节点是海，都不加入并查集
			if (x<0 || y < 0 || x >=n || y >= n) {
				continue
			}
			if grid[x][y] == 0 {
				continue
			}
			// 联通当前点 ij 和 四个方向的节点 xy。并统计面积
			union(p, sz, i*n + j + 1, x*n + y + 1)
			}
		}
	}
	  
	for i:=0; i<n; i++ {
		for j:=0; j<n; j++ {
			if grid[i][j] == 1 {
				// 找到当前节点所在集合的代表元素 find(p, i*n + j + 1)
				// 判断代表元素的 sz 面积是否是最大的，更新最大值
				ans = max(ans, sz[find(p, i*n + j + 1)])
			} else {
				// 待标记节点 visited 标记是否已被尝试填海
				tot := 1
				visited := map[int]bool{}
				for _, d := range dir {
					x, y := i+d[0], j+d[1]
					// 超界
					if (x < 0 || y < 0 || x >=n || y >= n) || grid[x][y] == 0 {
						continue
					}
					root := find(p, x*n + y + 1)
					if visited[root] {
						continue
					}
					tot += sz[root] // 找到根节点代表的面积
						visited[root] = true
					}
				ans = max(ans, tot)
			}
		}
	}
	return ans
}
  
func find(p []int, x int) int {
	if p[x] != x {
	// 路径压缩
		p[x] = find(p, p[x])
	}
	return p[x]
}
  
func union(p []int, sz []int, a, b int) {
	ra, rb := find(p, a), find(p, b)
	if ra == rb {
		// 同一联通集合
		return
	}
	// 将小面积的链接到大面积的区域
	if sz[ra] > sz[rb] {
		ra, rb = rb, ra
	}
	sz[rb] += sz[ra]
	p[ra] = p[rb]
	return
}