题意整理

  • 给定一个用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(mn)O(m*n)
  • 空间复杂度:需要额外大小为max(m,n)max(m,n)的递归栈,所以空间复杂度是O(max(m,n))O(max(m,n))

方法二(广度优先搜索)

1.思路整理

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

图解展示: alt

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(mn)O(m*n)
  • 空间复杂度:最坏情况下,需要额外大小为mnm*n的队列,所以空间复杂度是O(mn)O(m*n)