FatGod Blog
搜索 K

Appearance

🏝️ 岛屿的最大面积 ​

📝 题目描述 ​

​ 给你一个大小为m x n的二进制矩阵grid。

​ 岛屿是由一些相邻的 1 （代表土地）构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设grid的四个边缘都被 0 （代表水）包围着。

​ 岛屿的面积是岛上值为 1 的单元格的数目。

​ 计算并返回grid中最大的岛屿面积。如果没有岛屿，请返回面积为 0。

📋 代码模板 ​

java
class Solution {
    public int maxAreaOfIsland(int[][] grid) {

    }
}
java
function maxAreaOfIsland(grid: number[][]): number {
    
}

💡 提示 ​

  1. m==grid.length
  2. n==grid[i].length
  3. 1≤m≤50
  4. 1≤n≤50
  5. grid[i][j] 为 0 或 1

🚀 示例 ​

示例一 ​

​ 输入grid为[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]，输出为6。下图展示了网格中各个岛屿的面积。

示例一

示例二 ​

​ 输入grid为[[1,1,1,0,0,1],[1,1,0,1,0,0],[0,0,0,1,1,0],[0,1,1,1,0,1]]，输出为6。下图展示了网格中各个岛屿的面积。

示例二

示例三 ​

​ 输入grid为[[0,0,0,0,0,0,0,0]]，输出为0，这是因为网格图中不存在岛屿。

示例三

🖊️ 题解 ​

​ 该题本质上是在网格中找各个连通块的大小，并取最大值作为答案。

​ 我们可以初始化一个值为 0 的初始岛屿最大面积 maxArea，并扫描整个二维网格，如果单元格的值为 1，则以它为起始节点进行DFS或BFS。在搜索过程中，每遇到一个尚未访问过的陆地单元格（值为 1），就将其所属的连通分量大小加 1，并将该单元格标记为”已访问“。在搜索结束后，在当前连通分量大小与 maxArea 中选择一个较大值，并更新到变量 maxArea 中。

​ 为了进一步节省算法的空间，我们可以直接将网格中单元格的值更新为 2，表示其已经被访问。

DFS ​

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

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
                }
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1
                || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = VISITED;
        int area = 1;
        for (int d = 0; d < 4; d++) {
            area += dfs(grid, i + DIRS[d][0], j + DIRS[d][1]);
        }
        return area;
    }
}
typescript
const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const VISITED = 2;

function maxAreaOfIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    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] = VISITED;
        let area = 1;
        for (let d = 0; d < 4; d++) {
            area += dfs(i + DIRS[d][0], j + DIRS[d][1]);
        }
        return area;
    }
    let maxArea: number = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                maxArea = Math.max(maxArea, dfs(i, j));
            }
        }
    }
    return maxArea;
}

BFS ​

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

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int maxArea = 0;
        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] = VISITED;
                    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] = VISITED;
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
}
typescript
const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const VISITED = 2;

function maxAreaOfIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const queue: number[][] = [];
    let maxArea = 0;
    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] = VISITED;
                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] = VISITED;
                        }
                    }
                }
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    return maxArea;
}

💭 复杂度分析 ​

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

  • 时间复杂度：O(mn)。其中 m 与 n 分别为网格的行数和列数。
  • 空间复杂度：O(mn)。在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 mn。

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

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

上次更新于: