题解 | #岛屿的最大面积#

题意整理

• 给定一个用n*m矩阵表示的群岛的地图，其中1表示岛屿，0表示海洋。
• 求最大的岛屿的面积，两个岛屿相邻算同一个岛屿。

方法一（深度优先搜索）

1.思路整理

• 遍历所有的岛屿。
• 如果当前岛屿面积为1，则通过深度优先搜索（利用递归实现），找到与之相邻的所有的岛屿，计算其面积。
• 统计所有面积中的最大者，作为岛屿的最大面积。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    public int maxAreaIsland (int[][] grid) {
        int res=0;
        int m=grid.length;
        int n=grid[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //找到与这个岛相邻所有岛组成的面积，统计最大值
                if(grid[i][j]==1){
                    res=Math.max(res,dfs(grid,i,j));
                }
            }
        }
        return res;
    }
    
    //深度优先搜索
    private int dfs(int[][] grid,int i,int j){
        int m=grid.length;
        int n=grid[0].length;
        //超过边界，或者为0，或者已经访问过，直接返回0
        if(i<0||i>=m||j<0||j>=n||grid[i][j]==0){
            return 0;
        }
        //保证之后再访问的时候，面积不增加
        grid[i][j]=0;
        //向四个方向递归
        return dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1)+1;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历每一个岛屿一次，最坏情况下，地图上所有的格子都是岛屿，时间复杂度为$O(m\ast n)O(m*n)$。
• 空间复杂度：需要额外大小为$max(m,n)max(m,n)$的递归栈，所以空间复杂度是$O(max(m,n))O(max(m,n))$。

方法二（广度优先搜索）

1.思路整理

• 遍历所有的岛屿。
• 如果当前岛屿面积为1，则通过广度优先搜索（利用队列实现），找到与之相邻的所有的岛屿，计算其面积。
• 统计所有面积中的最大者，作为岛屿的最大面积。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    //方向数组
    int[][] dir=new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    
    public int maxAreaIsland (int[][] grid) {
        int res=0;
        int m=grid.length;
        int n=grid[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //找到与这个岛相邻所有岛组成的面积，统计最大值
                if(grid[i][j]==1){
                    res=Math.max(res,bfs(grid,i,j));
                }
            }
        }
        return res;
    }
    
    //广度优先搜索
    private int bfs(int[][] grid,int i,int j){
        int m=grid.length;
        int n=grid[0].length;
        Queue<int[]> queue=new LinkedList<>();
        //起始坐标放入队列
        queue.offer(new int[]{i,j});
        int cnt=0;
        while(!queue.isEmpty()){
            int[] cur=queue.poll();
            int x=cur[0];
            int y=cur[1];
            //越界，或者为0，或者已访问
            if(x<0||x>=m||y<0||y>=n||grid[x][y]==0){
                continue;
            }
            //标记为0
            grid[x][y]=0;
            //面积加1
            cnt++;
            //往四个方向搜索
            for(int k=0;k<4;k++){
                int dx=x+dir[k][0];
                int dy=y+dir[k][1];
                //加入到队列
                queue.offer(new int[]{dx,dy});
            }
        }
        return cnt;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历每一个岛屿一次，最坏情况下，地图上所有的格子都是岛屿，时间复杂度为$O(m\ast n)O(m*n)$。
• 空间复杂度：最坏情况下，需要额外大小为$m\ast nm*n$的队列，所以空间复杂度是$O(m\ast n)O(m*n)$。