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

岛屿的最大面积

题目描述 给定一个用 n*m 矩阵表示的群岛的地图，其中 1 表示岛屿， 0 表示海洋，每个岛屿的水平或竖直方向相邻的岛屿可以视为连在一起的岛屿，每一块岛屿视为面积为 1 ，请问面积最大的岛屿是多少。

方法一：dfs方法

解题思路

对于本题，采用dfs思想进行求解，利用dfs扩展岛屿的面积，然后维护面积的最大值。注意。dfs要用递归来遍历四个方向，不断访问可以访问的点。

解题代码

class Solution {
public:
    int vis[50][50]={0};//根据题目进行数组大小的选择
    int a[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//四个方向
    int res=0,n,m;
    int cnt;
    int maxAreaIsland(vector<vector<int> >& grid)
    {
        n=grid.size();
        if(n==0)
            return 0;
        m=grid[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(vis[i][j]==0&&grid[i][j]==1)
                {//如果未访问过，则访问
                    cnt=0;
                    dfs(i,j,grid);
                    res=max(cnt,res);//维护最大值
                }
            }
        }
        return res;
    }
    void dfs(int x,int y,vector<vector<int> >& grid)
    {
        vis[x][y]=1;
        cnt++;//面积加一
        for(int i=0;i<4;i++)
        {//遍历四个方向
            int nx=x+a[i][0],ny=y+a[i][1];
            if(nx<0||nx>=n||ny<0||ny>=m)
            {//下标越界判断
                continue;
            }
            if(vis[nx][ny]==0&&grid[nx][ny]==1)
            {//如果未访问过，则访问
                dfs(nx,ny,grid);
            }
        }
    }
};

复杂度分析

时间复杂度：每个节点都访问一遍，因此时间复杂度为$O(n\ast m)O(n*m)$。

空间复杂度：存储vis数组和递归栈深度，因此空间复杂度为$O(n\ast m)O(n*m)$。

方法二：bfs方法

解题思路

本题目也可也使用bfs的思想，利用bfs扩展岛屿的面积，然后维护面积的最大值。注意，bfs要用队列遍历四个方向，不断访问可以访问的点。

解题代码

class Solution {
public:
    int vis[50][50]={0};
    int a[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//四个方向
    int res=0,n,m;
    int cnt;
    int maxAreaIsland(vector<vector<int> >& grid)
    {
        n=grid.size();
        if(n==0)
            return 0;
        m=grid[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(vis[i][j]==0&&grid[i][j]==1)
                {//如果未访问过，则访问
                    bfs(i,j,grid);
                    res=max(cnt,res);//维护最大值
                }
            }
        }
        return res;
    }
    void bfs(int x,int y,vector<vector<int> >& grid){
        queue<pair<int,int>> q;//队列
        q.push({x,y});//入队
        vis[x][y]=1;
        cnt=1;//面积初始化为1
        while(!q.empty())
        {
            auto t=q.front();
            q.pop();//出队
            for(int i=0;i<4;i++)
            {//遍历四个方向
                int nx=t.first+a[i][0],ny=t.second+a[i][1];
                if(nx<0||nx>=n||ny<0||ny>=m)
                {//下标越界判断
                    continue;
                }
                if(vis[nx][ny]==0&&grid[nx][ny]==1)
                {//如果未访问过，则访问
                    q.push({nx,ny});
                    vis[nx][ny]=1;
                    cnt++;
                }
            }
        }
    }
};

复杂度分析

时间复杂度：每个节点都访问一遍，因此时间复杂度为$O(n\ast m)O(n*m)$。

空间复杂度：存储vis数组和队列，因此空间复杂度为$O(n\ast m)O(n*m)$。