题目形容
这是 LeetCode 上的 827. 最大人工岛 ，难度为 艰难。
Tag : 「并查集」、「枚举」
给你一个大小为 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 = 510const 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/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布