【2022-09-18每日一题】827. 最大人工岛

2022-09-18每日一题：827. 最大人工岛

难度：Hard

标签：深度优先搜索 、 广度优先搜索 、 并查集 、 数组 、 矩阵

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

方法一：标记岛屿 + 合并（DFS）

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func largestIsland(grid [][]int) (ans int) {
    dir4 := []struct{x, y int}{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
    n, t := len(grid), 0
    tag := make([][]int, n) // 保存i,j所属岛屿
    for i := range tag {
        tag[i] = make([]int, n)
    }
    area := make(map[int]int)
    var dfs func(int, int)
    dfs = func(i, j int) {
        tag[i][j] = t // 保存i,j所属岛屿
        area[t]++
        for _, d := range dir4 {
            x, y := i + d.x, j + d.y
            if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] > 0 && tag[x][y] == 0 {
                dfs(x, y)
            }
        }
    }
    // 计算岛屿
    for i, row := range grid {
        for j, x := range row {
            // 枚举没有访问过的陆地
            if x > 0 && tag[i][j] == 0 {
                t = n * i + j + 1
                dfs(i, j)
                ans = max(ans, area[t])
            }
        }
    }
    // 假设把0->1
    for i, row := range grid {
        for j, x := range row {
            // 枚举可以添加陆地的位置
            if x == 0 {
                newArea := 1
                connected := map[int]bool{0:true}
                for _, d := range dir4 {
                    x, y := i + d.x, j + d.y
                    if 0 <= x && x < n && 0 <= y && y < n && !connected[tag[x][y]] {
                        newArea += area[tag[x][y]]
                        connected[tag[x][y]] = true
                    }
                }
                ans = max(ans, newArea)
            }
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是 grid 的长与宽。使用深度优先搜索获取岛屿面积时，总共访问不超过 n^2个点。

• 空间复杂度：O(n^2)。保存 tag 与area 需要 O(n^2)的空间。

方法二：并查集

参考讲解

• https://leetcode.cn/problems/making-a-large-island/solution/by-ac_oier-1kmp/

• https://leetcode.cn/problems/making-a-large-island/solution/by-lcbin-f4c1/

func largestIsland(grid [][]int) int {
    dir4 := []struct{x, y int}{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
    n := len(grid)
    p, size := make([]int, n*n), make([]int, n*n)
    for i := range p {
        p[i] = i
        size[i] = 1
    }
    // 并查集find
    var find func(int) int
    find = func(x int) int {
        if p[x] != x { // 压缩路径
            p[x] = find(p[x])
        }
        return p[x]
    }
    ans := 1 // [[1]] 用例
    for i, row := range grid {
        for j, x := range row {
            if x == 1 {
                for _, d := range dir4 {
                    x, y := i+d.x, j+d.y
                    if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 1 {
                        // 相当于并查集 union
                        pa, pb := find(x*n+y), find(i*n+j)
                        if pa != pb {
                         	p[pa] = pb
                            size[pb] += size[pa]
                            ans = max(ans, size[pb])
                        }
                    }
                }
            } 
        }
    }
    
    for i, row := range grid {
        for j, x := range row {
            if x == 0 {
                t := 1
                vis := map[int]struct{}{}
                for _, d := range dir4 {
                    x, y := i+d.x, j+d.y
                    if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 1 {
                        // 相当于并查集 union
                        root := find(x*n+y)
                        if _, ok := vis[root]; !ok {
                            vis[root] = struct{}{}
                            t += size[root]
                        }
                    }
                }
                ans = max(ans, t)
            } 
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

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

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

LeetCode题库地址

• https://leetcode.cn/problems/making-a-large-island