🏝️ 最大人工岛

📝 题目描述

给你一个大小为n x n二进制矩阵grid。最多只能将一格0变成1。

返回执行此操作后，grid中最大的岛屿面积是多少？

岛屿是一组由上、下、左、右四个方向相连的1组成。

📋 代码模板

javatypescript

java

class Solution {
    public int largestIsland(int[][] grid) {

    }
}

typescript

function largestIsland(grid: number[][]): number {

}

💡 提示

$n == g r i d . l e n g t h$
$n == g r i d [i] . l e n g t h$
$1 \leq n \leq 500$
$g r i d [i] [j]$ 为0或1

🚀 示例

示例一

输入grid为[[0,1,1,0,1,1],[1,0,0,1,0,1],[1,1,0,1,0,0],[1,1,1,0,0,1],[0,0,0,1,1,1]]，输出为13。如下图所示，在人工填充一个海洋单元格之后，岛屿达到了最大面积。其中，我们用绿色来标记构成最大岛屿的陆地单元格，而用五角星来标记刚刚被填充的海洋单元格。

示例一

示例二

输入grid为[[1,0],[0,1]]，输出为3。如下图所示，在人工填充一个海洋单元格之后，岛屿达到了最大面积。其中，我们用绿色来标记构成最大岛屿的陆地单元格，而用五角星来标记刚刚被填充的海洋单元格。

示例二

示例三

输入grid为[[1,1],[1,0]]，输出为4。如下图所示，在人工填充一个海洋单元格之后，岛屿达到了最大面积。其中，我们用绿色来标记构成最大岛屿的陆地单元格，而用五角星来标记刚刚被填充的海洋单元格。

示例三

示例四

输入grid为[[1,1],[1,1]]，输出为4。该网格中所有单元格都为陆地，因此它不需要填充海洋单元格，答案为网格中单元格的总数。

示例四

🖊️ 题解

解决本题的关键在于找到一个海洋单元格，将其填充为陆地后，能够使得网格中形成的单个岛屿面积达到最大。因此，我们需要枚举网格中的每一个海洋单元格，并计算出其被填充后所形成的岛屿面积，最后取最大值，即为答案。

对于每一个海洋单元格，其被填充后形成的岛屿面积的计算方式为：上下左右四个相邻方向上的单元格所处的连通分量大小相加后的结果再加 $1$ ，如果相邻单元格为海洋或者超出网格边缘，那么它的连通分量大小可视为 $0$ 。例如，在下图中，使用靶心标记的海洋单元格被填充后所形成的岛屿面积为： $2 + 2 + 0 + 0 + 1 = 5$ 。

填充海洋单元格后岛屿的计算方式

需要注意的是，四个方向上相邻的陆地单元格可能处于同一连通分量。例如，在下图中，靶心单元格上方和右方相邻的陆地单元格处于同一连通分量，大小为 $5$ 。在这种情况下，这两个方向上的连通分量大小在计算岛屿面积时只能被累加一次。

填充海洋单元格的特殊情况

首先，我们可以通过DFS或BFS来标记网格中的每一个独立的连通分量，并将这些连通分量中的所有陆地单元格的值更新为特定的标识号。标识号可以从 $2$ 开始，这是因为网格中单元格的原始值只为 $0$ 或 $1$ ，被标识的陆地单元格的状态可以视为“已访问”。例如，下图展示了示例一中网格的标识填充过程。

示例一中的标识填充

其次，为了快速获取特定标识的连通分量大小，我们可以在搜索过程中维护一个哈希表，该表将“连通分量标识号”与“连通分量大小”进行映射。例如，下图展示了示例一中所有连通分量经过搜索后形成的哈希表。

示例一中的哈希表

最后，遍历二维网格中的每个海洋单元格，计算出其被填充后形成的岛屿面积，并取最大值。

DFS

javatypescript

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final static int OFFSET_START = 2;

    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, maxArea = 0;
        int offset = OFFSET_START;
        Map<Integer, Integer> table = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, offset);
                    table.put(offset, area);
                    offset++;
                    maxArea = area;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> set = new HashSet<>(4);
                    int area = 1;
                    for (int d = 0; d < 4; d++) {
                        int nextI = i + DIRS[d][0], nextJ = j + DIRS[d][1];
                        if (nextI < 0 || nextI > m - 1 || nextJ < 0 || nextJ > n - 1
                                || grid[nextI][nextJ] == 0 || set.contains(grid[nextI][nextJ])) {
                            continue;
                        }
                        area += table.get(grid[nextI][nextJ]);
                        set.add(grid[nextI][nextJ]);
                    }
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int i, int j, int offset) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = offset;
        int area = 1;
        for (int d = 0; d < 4; d++) {
            area += dfs(grid, i + DIRS[d][0], j + DIRS[d][1], offset);
        }
        return area;
    }
}

typescript

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const OFFSET_START = 2;

function largestIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    let offset = OFFSET_START, maxArea = 0;
    const dfs = (i: number, j: number): number => {
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = offset;
        let area = 1;
        for (let d = 0; d < 4; d++) {
            area += dfs(i + DIRS[d][0], j + DIRS[d][1]);
        }
        return area;
    }
    const table = new Map<number, number>();
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                const area = dfs(i, j);
                table.set(offset, area);
                offset++;
                maxArea = area;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                const set = new Set<number>();
                let area = 1;
                for (let d = 0; d < 4; d++) {
                    const nextI = i + DIRS[d][0], nextJ = j + DIRS[d][1];
                    if (nextI < 0 || nextI > m - 1 || nextJ < 0 || nextJ > n - 1
                        || grid[nextI][nextJ] == 0 || set.has(grid[nextI][nextJ])) {
                        continue;
                    }
                    area += table.get(grid[nextI][nextJ])!;
                    set.add(grid[nextI][nextJ]);
                }
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    return maxArea;
}

BFS

javatypescript

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final static int OFFSET_START = 2;

    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, maxArea = 0;
        int offset = OFFSET_START;
        Map<Integer, Integer> table = new HashMap<>();
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = 1;
                    queue.offer(new int[]{i, j});
                    grid[i][j] = offset;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int oldI = cell[0], oldJ = cell[1];
                        for (int d = 0; d < 4; d++) {
                            int currentI = oldI + DIRS[d][0], currentJ = oldJ + DIRS[d][1];
                            if (currentI >= 0 && currentI < m && currentJ >= 0 && currentJ < n
                                    && grid[currentI][currentJ] == 1) {
                                area++;
                                queue.offer(new int[]{currentI, currentJ});
                                grid[currentI][currentJ] = offset;
                            }
                        }
                    }
                    table.put(offset, area);
                    offset++;
                    maxArea = area;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> set = new HashSet<>(4);
                    int area = 1;
                    for (int d = 0; d < 4; d++) {
                        int nextI = i + DIRS[d][0], nextJ = j + DIRS[d][1];
                        if (nextI < 0 || nextI > m - 1 || nextJ < 0 || nextJ > n - 1
                                || grid[nextI][nextJ] == 0 || set.contains(grid[nextI][nextJ])) {
                            continue;
                        }
                        area += table.get(grid[nextI][nextJ]);
                        set.add(grid[nextI][nextJ]);
                    }
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        return maxArea;
    }
}

typescript

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const OFFSET_START = 2;

function largestIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    let offset = OFFSET_START, maxArea = 0;
    const table = new Map<number, number>();
    const queue: number[][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                let area = 1;
                queue.push([i, j]);
                grid[i][j] = offset;
                while (queue.length > 0) {
                    const cell: number[] = queue.shift()!;
                    const oldI = cell[0], oldJ = cell[1];
                    for (let d = 0; d < 4; d++) {
                        const currentI = oldI + DIRS[d][0], currentJ = oldJ + DIRS[d][1];
                        if (currentI >= 0 && currentI < m && currentJ >= 0 && currentJ < n
                            && grid[currentI][currentJ] == 1) {
                            area++;
                            queue.push([currentI, currentJ]);
                            grid[currentI][currentJ] = offset;
                        }
                    }
                }
                table.set(offset, area);
                offset++;
                maxArea = area;
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                const set = new Set<number>();
                let area = 1;
                for (let d = 0; d < 4; d++) {
                    const nextI = i + DIRS[d][0], nextJ = j + DIRS[d][1];
                    if (nextI < 0 || nextI > m - 1 || nextJ < 0 || nextJ > n - 1
                        || grid[nextI][nextJ] == 0 || set.has(grid[nextI][nextJ])) {
                        continue;
                    }
                    area += table.get(grid[nextI][nextJ])!;
                    set.add(grid[nextI][nextJ]);
                }
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    return maxArea;
}

💭 复杂度分析

基于DFS的解决方案的复杂度分析如下。

时间复杂度： $O (m n)$ 。其中 $m$ 与 $n$ 分别为网格的行数和列数。
空间复杂度： $O (m n)$ 。

基于BFS的解决方案的复杂度分析如下。

时间复杂度： $O (m n)$ 。其中 $m$ 与 $n$ 分别为网格的行数和列数。
空间复杂度： $O (m n)$ 。

🏝️ 最大人工岛 ​

📝 题目描述 ​

📋 代码模板 ​

💡 提示 ​

🚀 示例 ​

示例一 ​

示例二 ​

示例三 ​

示例四 ​

🖊️ 题解 ​

DFS ​

BFS ​

💭 复杂度分析 ​

🏝️ 最大人工岛

📝 题目描述

📋 代码模板

💡 提示

🚀 示例

示例一

示例二

示例三

示例四

🖊️ 题解

DFS

BFS

💭 复杂度分析