【Day 50 】2023-04-04 - 695. 岛屿的最大面积

[azl397985856]

695. 岛屿的最大面积

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/max-area-of-island/

前置知识

暂无

题目描述

给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 （代表土地） 构成的组合，
这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。（如果没有岛屿，则返回面积为 0 。)

示例 1:

[[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。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵，返回 0。

 
注意：给定的矩阵 grid 的长度和宽度都不超过 50

[JiangyanLiNEU]

• DFS

  class Solution:
  def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
      self.res = 0
      directions = [[1,0],[-1,0],[0,1],[0,-1]]
  
      def inBound(row, col):
          return row >= 0 and col >= 0 and row <len(grid) and col < len(grid[0])
  
      def dfs(row, col, seen, cur):
          for dx, dy in directions:
              newR = row+dx
              newC = col+dy
              if inBound(newR, newC) and (newR, newC) not in seen and grid[newR][newC] == 1:
                  seen.add((newR, newC))
                  cur += dfs(newR, newC, seen, 1)
                  grid[newR][newC] = 2
          return cur
  
      for row in range(len(grid)):
          for col in range(len(grid[0])):
              if grid[row][col] == 1:
                  self.res = max(self.res, dfs(row, col, set([(row, col)]), 1))
      return self.res

• BFS

  class Solution:
  def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
      self.res = 0
      directions = [[1,0],[-1,0],[0,1],[0,-1]]
  
      def inBound(row, col):
          return row >= 0 and col >= 0 and row <len(grid) and col < len(grid[0])
  
      def bfs(row, col, seen):
          island = 0
          qualified = [(row, col)]
          while qualified:
              island += 1
              row, col = qualified.pop(0)
              for dx, dy in directions:
                  newR, newC = row+dx, col+dy
                  if inBound(newR, newC) and grid[newR][newC] == 1 and (newR, newC) not in seen:
                      seen.add((newR, newC))
                      qualified.append((newR, newC))
                      grid[newR][newC] = 2
          return island
      for row in range(len(grid)):
          for col in range(len(grid[0])):
              if grid[row][col] == 1:
                  self.res = max(self.res, bfs(row, col, set([(row, col)])))
      return self.res

[huifeng248]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        visited = set()
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if (i, j) not in visited:
                    count = self.dfs(i, j, visited, grid)
                    res = max(res, count)

        return res

    def dfs(self, row, col, visited, grid):
        stack = [(row, col)]
        count = 0
        while stack:
            r, c = stack.pop()
            if (r, c) not in visited and grid[r][c] == 1:
                count += 1
                visited.add((r,c))

            dirs = [[1,0], [-1,0], [0,-1], [0,1]]
            for point in dirs:
                n_r = r + point[0]
                n_c = c + point[1]
                valid_row = 0 <= n_r < len(grid)
                valid_col = 0 <= n_c < len(grid[0])
                if valid_row and valid_col and (n_r, n_c) not in visited and grid[r][c] == 1:
                    stack.append((n_r, n_c))

        return count 
# time complexity: O(mn) m is len of row, and n is the len of col.
# space complexity:O(mn) m is len of row, and n is the len of col.

[bingzxy]

思路

dfs

代码

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

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = 2;
        return dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1) + 1;
    }
}

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(1)

[Abby-xu]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(x,y):
            if grid[x][y] == 1:
                grid[x][y] = -1
                res = 1
            else:
                return 0
            if x + 1 < len(grid):
                res += dfs(x+1,y) 
            if x - 1 >= 0:
                res += dfs(x-1,y) 
            if y + 1 < len(grid[0]):
                res += dfs(x,y+1)
            if y - 1 >= 0:
                res += dfs(x,y-1)
            return res

        seen = set()
        max_area = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i,j))

        return max_area

[kofzhang]

思路

深度优先搜索

复杂度

时间复杂度：O(mn) 空间复杂度：O(1)

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])

        def dfs(m,n):
            if m<0 or m>=row or n<0 or n>=col or grid[m][n]!=1:
                return 0
            cnt = 1
            grid[m][n]=0
            cnt +=dfs(m-1,n)+dfs(m+1,n)+dfs(m,n-1)+dfs(m,n+1)
            return cnt
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j]==1:
                    res = max(res,dfs(i,j))
        return res

[yingchehu]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(x, y):
            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
                return 0
            if grid[x][y] == 0:
                return 0
            grid[x][y] = 0
            return 1 + dfs(x+1, y) + dfs(x-1, y) + dfs(x, y+1) + dfs(x, y-1)
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                ans = max(ans, dfs(i, j))
        return ans

[wangzh0114]

class Solution {
    int getArea(vector<vector<int>>&  grid, int i, int j){
        if (i == grid.size() || i < 0)
            return 0;
        else if (j == grid[0].size() || j < 0)
            return 0; ;
        if (grid[i][j] == 1){
            grid[i][j] = 0;
            return 1 + getArea(grid, i + 1, j) + getArea(grid, i - 1, j ) + getArea(grid, i, j + 1) + getArea(grid, i, j - 1);
        }
        return 0;
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxArea = 0;
        int area = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 1)
                {
                    area = getArea(grid, i, j);
                    maxArea = maxArea > area ? maxArea : area;
                }
            }
        }
        return maxArea;
    }
};

• TC:O(mn)
• SC:O(mn)

[jackgaoyuan]

func maxAreaOfIsland(grid [][]int) int {

 m := len(grid)
  n := len(grid[0])
  ans := 0
  //方向数组
  dx := []int{-1,0,0,1}
  dy := []int{0,-1,1,0}

   //初始化并查集
   fa := make([]int, m*n+1)
   rank := make([]int, m*n+1)
    for i:=0;i<=m*n;i++{
        fa[i] = i
    }
    for i:=0;i<=m*n;i++{
        rank[i] = 1
    }

   //循环网格

    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
           //如果碰到水则continue
           if (grid[i][j] == 0){continue}

           for k:=0;k<4;k++{

               nx := i + dx[k]
               ny := j + dy[k]

               //到了边界continue
               if (nx>=m || ny >=n||nx<0||ny<0){
                   continue

                //如果相邻是1，则加入并查集 uninonset   
               }

                if grid[nx][ny] == 1{
                       unionSet(fa,rank, nums(n, i, j), nums(n,nx,ny))
                   }
               }
           }

        }

    //最后查找并查集的最大秩即可，最大秩在根节点上
    for i:=0;i<m;i++{
      for j:=0;j<n;j++{

          if (grid[i][j] ==1&&Find(fa, nums(n,i,j)) == nums(n,i,j)){

              ans = max(ans, rank[nums(n,i,j)])
          }

      }

    }

    return ans 

}

func nums(n, i, j int) int {
    return i*n+j
}

func max(a, b int) int{
    if (a>b){
        return a
    }else{
        return b 
    }
}

func Find(fa []int, x int ) int {
    if (fa[x]==x){return  x}
     fa[x] = Find(fa, fa[x])
     return fa[x]
}  
//并查集按照秩合并，小的秩加到大的里面

func unionSet(fa []int, rank []int , x, y int ) {
    x, y = Find(fa, x), Find(fa, y) 
    if (x !=y){
        if (rank[x]<=rank[y]){
            fa[x] = y
            rank[y] += rank[x]
        }else {
            fa[y] = x
            rank[x] += rank[y]
        }
    }
}

[NorthSeacoder]

var maxAreaOfIsland = function(grid) {
    let maxArea = 0; // 记录最大面积
    const row = grid.length; // 行数
    const col = grid[0].length; // 列数

    // 定义 DFS 函数，计算联通块面积
    const dfs = (i, j) => {
        if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] === 0) {
            return 0;
        }
        grid[i][j] = 0; // 将当前位置标记为已访问
        // 递归计算联通块面积
        return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1);
    };

    // 遍历整个矩阵，找到每个联通块的面积
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] === 1) {
                // 如果当前位置为 1，说明是一个联通块的起点
                maxArea = Math.max(maxArea, dfs(i, j)); // 计算联通块面积，并更新最大面积
            }
        }
    }
    return maxArea; // 返回最大面积
};

• TC: O(mn)
• SC:O(mn)

[JadeLiu13]

py3

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        res=0
        row,column=len(grid),len(grid[0])
        moveset=[(0,1),(1,0),(-1,0),(0,-1)]

        def dfs(grid,i,j):
            if i < 0 or j<0 or i>=row or j>=column or grid[i][j] == 0:
                return 0            
            s=1
            grid[i][j]=0
            for cood in moveset:
                s+=dfs(grid,i+cood[0],j+cood[1])
            return s

        for i in range(row):
            for j in range(column):
                if grid[i][j]==1:
                    res=max(res,dfs(grid,i,j))            
        return res

[duke-github]

思路

dfs 深度优先遍历 已遍历过的置0

复杂度

时间复杂度O(m*n) 空间复杂度O(m*n)

代码

class Solution {
   public int maxAreaOfIsland(int[][] grid) {
        int size = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                size = Math.max(size, dfs(i, j, grid));

            }
        }
        return size;
    }

    public int[][] position = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int dfs(int x, int y, int[][] grid) {
        if (x < 0 || y < 0 || x == grid.length || y == grid[0].length || grid[x][y] == 0) {
            return 0;
        }

        grid[x][y] = 0;
        int size = 1;
        for (int i = 0; i < 4; i++) {
            int newX = x + position[i][0];
            int newY = y + position[i][1];
            size += dfs(newX, newY, grid);
        }
        return size;
    }
}

[zhangyu1131]

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        // dfs

        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> visited(n, vector<int>(m, 0));// 记录是否遍历过

        int max_area = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j] == 1 && !visited[i][j])
                {
                    int tmp_area = 0;
                    dfs(grid, i, j, visited, tmp_area);
                    max_area = std::max(max_area, tmp_area);
                }
            }
        }

        return max_area;
    }
private:
    void dfs(const vector<vector<int>>& grid, int i, int j, vector<vector<int>>& visited, int& area)
    {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || visited[i][j])
        {
            return;
        }
        if (grid[i][j] == 0) // 海洋
        {
            return;
        }

        // 符合条件
        ++area;
        visited[i][j] = 1;

        // dfs查周围的四个方向
        dfs(grid, i - 1, j, visited, area);
        dfs(grid, i + 1, j, visited, area);
        dfs(grid, i, j - 1, visited, area);
        dfs(grid, i, j + 1, visited, area);
    }
};

[FireHaoSky]

思路：dfs

代码：python

class Solution:
    def dfs(self,grid,cur_i, cur_j):
        if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
            return 0
        grid[cur_i][cur_j] = 0
        ans = 1
        for di, dj in [[1,0],[-1,0],[0,1],[0,-1]]:
            next_i, next_j = cur_i + di, cur_j + dj
            ans += self.dfs(grid, next_i, next_j)
        return ans
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, l in enumerate(grid):
            for j, n in enumerate(l):
                ans = max(self.dfs(grid,i,j), ans)
        return ans

复杂度分析：

"""
时间复杂度：O(nxm)
空间复杂度：O(nxm)
"""

[bookyue]

SC: O(n)
TC: O(1)

dfs

    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 1) continue;

                ans = Math.max(ans, dfs(grid, i, j));
            }
        }

        return ans;
    }

    private int dfs(int[][] grid, int x, int y) {
        grid[x][y] = 0;
        int area = 1;
        for (int[] dir : DIRS) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length
                    && grid[nx][ny] == 1)
                area += dfs(grid, nx, ny);
        }

        return area;
    }

union-find

    private static final int[][] DIRS = {{1, 0}, {0, 1}};

    private int[] parent;
    private int[] size;

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        if (m == 1 && n == 1) return grid[0][0];

        parent = new int[m * n];
        size = new int[m * n];
        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        int ans = 0;
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                if (grid[x][y] == 0) continue;

                ans = Math.max(ans, grid[x][y]);
                for (int[] dir : DIRS) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];

                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1)
                        ans = Math.max(ans, union(x * n + y, nx * n + ny));
                }
            }
        }

        return ans;
    }

    private int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }

        return p;
    }

    private int union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return size[pRoot];

        if (size[pRoot] >= size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }

        return Math.max(size[pRoot], size[qRoot]);
    }

[tzuikuo]

思路

广度优先

代码

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> record(m,vector<int>(n,0));
        vector<vector<int>> direct={{0,1},{0,-1},{1,0},{-1,0}};
        int cnt=0,remax=INT_MIN;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1&&record[i][j]==0){
                    int ii,jj;
                    queue<vector<int>> myque;
                    cnt=0;
                    myque.push({i,j});
                    record[i][j]=1;
                    while(!myque.empty()){
                        cnt++;
                        vector<int> curvec;
                        curvec=myque.front();
                        myque.pop();
                        ii=curvec[0];
                        jj=curvec[1];
                        for(int k=0;k<=3;k++){
                            if(ii+direct[k][0]<m&&ii+direct[k][0]>=0&&jj+direct[k][1]<n&&jj+direct[k][1]>=0&&grid[ii+direct[k][0]][jj+direct[k][1]]==1&&record[ii+direct[k][0]][jj+direct[k][1]]==0){
                                myque.push({ii+direct[k][0],jj+direct[k][1]});
                                record[ii+direct[k][0]][jj+direct[k][1]]=1;
                            }
                        }
                    }
                    if(cnt>remax) remax=cnt;
                }
                else continue;
            }
        }
        if(remax==INT_MIN) return 0; 
        return remax;
    }
};

复杂度分析 -时间 O(n^2) -空间 O(n^2)

[sye9286]

思路

深度优先遍历网格， 当找到 1 时，将当前单元格置为0防止重复遍历，然后上下左右递归，计算出每个岛屿的大小，最后返回最大岛屿

代码

var maxAreaOfIsland = function(grid) {
    let row = grid.length, col = grid[0].length;
    function dfs (x, y) {
        if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] === 0) return 0
        grid[x][y] = 0
        let ans = 1, dx = [-1, 1, 0, 0], dy = [0, 0, 1, -1]
        for (let i = 0; i < dx.length; i++) {
            ans += dfs(x + dx[i], y + dy[i])
        }
        return ans
    }

    let res = 0;
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            res = Math.max(res, dfs(i, j))
        }
    }
    return res
};

复杂度分析

• 时间复杂度：O(m*n)
• 空间复杂度：O(m*n)

[Meisgithub]

class Solution {
public:
    int ans = 0;
    int neighbors[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1 && !visited[i][j])
                {
                    traverse(grid, i, j, visited);
                }
            }
        }
        return ans;
    }

    void traverse(const vector<vector<int>>& grid, int row, int col, vector<vector<int>> &visited)
    {
        int m = grid.size();
        int n = grid[0].size();
        queue<pair<int, int>> q;
        q.emplace(row, col);
        visited[row][col] = 1;
        int count = 0;
        while (!q.empty())
        {
            pair<int, int> pos = q.front();
            q.pop();
            count++;
            for (auto &neighbor : neighbors)
            {
                int newRow = pos.first + neighbor[0];
                int newCol = pos.second + neighbor[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1 && !visited[newRow][newCol])
                {
                    q.emplace(newRow, newCol);
                    visited[newRow][newCol] = 1;
                }
            }
        }

        ans = max(ans, count);
    }
};

[harperz24]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0
        visited = set()

        def dfs(r, c):
            if not (0 <= r < len(grid) and 0 <= c < len(grid[0])):
                return 0
            if (r, c) in visited:
                return 0 
            if grid[r][c] == 0:
                return 0
            visited.add((r, c))
            area = 1
            for dir_r, dir_c in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                area += dfs(r + dir_r, c + dir_c)
            return area

        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    max_area = max(max_area, dfs(r, c))
        return max_area

        # matrix dfs
        # time: O(r * c)
        # time: O(r * c)

[aoxiangw]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        m = len(grid)
        n = len(grid[0])
        ans = 0
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return 0
            if grid[i][j] == 0:
                return 0
            grid[i][j] = 0
            top = dfs(i - 1, j)
            bottom = dfs(i + 1, j)
            left = dfs(i, j - 1)
            right = dfs(i, j + 1)
            return 1 + sum([top, bottom, left, right])
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j))
        return ans

O(mn), O(mn)

[wangqianqian202301]

思路

bfs

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        visited = set()
        curArea = 0
        maxArea = 0

        def bfs(r,c):
            queue = collections.deque()
            area = 1
            queue.append((r,c))
            visited.add((r,c))
            while queue:
                row, col = queue.popleft()
                directions = [
                    [1,0],     
                    [-1,0],    
                    [0,1],     
                    [0,-1]     
                ]
                for dr, dc in directions:
                    r,c = row+dr,col+dc
                    if (
                            r in range(rows) and
                            c in range(cols) and
                            grid[r][c] == 1 and
                            (r,c) not in visited
                    ):
                        visited.add((r,c))
                        queue.append((r,c))
                        area += 1
            return area

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and (r,c) not in visited:
                    curArea = bfs(r,c)
                    maxArea = max(maxArea, curArea)

        return maxArea

[Jetery]

class Solution {
public:
    int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int row, col, ans;

    int dfs(int i, int j, vector<vector<int>>& grid, vector<vector<bool>>& vis) {
        if (i < 0 || j < 0 || i == row || j == col || vis[i][j]) return 0;
        int cur = 0;
        if (grid[i][j] == 1) {
            vis[i][j] = true;
            cur ++;
            for (auto dir : dirs) {
                int x = i + dir[0];
                int y = j + dir[1];
                cur += dfs(x, y, grid, vis);
            }
        }
        return cur;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        row = grid.size(), col = grid[0].size();
        vector<vector<bool>> vis(row, vector<bool>(col, false));
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    ans = max(ans, dfs(i, j, grid, vis));
                }
            }
        }
        return ans;
    }
};

[joemonkeylee]

思路

dfs

代码

       public int MaxAreaOfIsland(int[][] grid)
        {
            int ans = 0;
            for (int i = 0; i != grid.Length; ++i)
            {
                for (int j = 0; j != grid[0].Length; ++j)
                {
                    ans = Math.Max(ans, dfs(grid, i, j));
                }
            }
            return ans;
        }

        public int dfs(int[][] grid, int cur_i, int cur_j)
        {
            if (cur_i < 0 || cur_j < 0 || cur_i == grid.Length || cur_j == grid[0].Length || grid[cur_i][cur_j] != 1)
            {
                return 0;
            }
            grid[cur_i][cur_j] = 0;
            int[] di = { 0, 0, 1, -1 };
            int[] dj = { 1, -1, 0, 0 };
            int ans = 1;
            for (int index = 0; index != 4; ++index)
            {
                int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                ans += dfs(grid, next_i, next_j);
            }
            return ans;
        }

复杂度分析

• 时间复杂度：O(m*n)
• 空间复杂度：O(m*n)

[Hughlin07]

class Solution {

public int maxAreaOfIsland(int[][] grid) {
    boolean[][] seen = new boolean[grid.length][grid[0].length];
    int[] dr = new int[]{1, -1, 0, 0};
    int[] dc = new int[]{0, 0, 1, -1};

    int ans = 0;
    for (int r0 = 0; r0 < grid.length; r0++) {
        for (int c0 = 0; c0 < grid[0].length; c0++) {
            if (grid[r0][c0] == 1 && !seen[r0][c0]) {
                int shape = 0;
                Stack<int[]> stack = new Stack();
                stack.push(new int[]{r0, c0});
                seen[r0][c0] = true;
                while (!stack.empty()) {
                    int[] node = stack.pop();
                    int r = node[0], c = node[1];
                    shape++;
                    for (int k = 0; k < 4; k++) {
                        int nr = r + dr[k];
                        int nc = c + dc[k];
                        if (0 <= nr && nr < grid.length &&
                                0 <= nc && nc < grid[0].length &&
                                grid[nr][nc] == 1 && !seen[nr][nc]) {
                            stack.push(new int[]{nr, nc});
                            seen[nr][nc] = true;
                        }
                    }
                }
                ans = Math.max(ans, shape);
            }
        }
    }
    return ans;
}

}

[enrilwang]

class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: self.res = 0 directions = [[1,0],[-1,0],[0,1],[0,-1]]

    def inBound(row, col):
        return row >= 0 and col >= 0 and row <len(grid) and col < len(grid[0])

    def bfs(row, col, seen):
        island = 0
        qualified = [(row, col)]
        while qualified:
            island += 1
            row, col = qualified.pop(0)
            for dx, dy in directions:
                newR, newC = row+dx, col+dy
                if inBound(newR, newC) and grid[newR][newC] == 1 and (newR, newC) not in seen:
                    seen.add((newR, newC))
                    qualified.append((newR, newC))
                    grid[newR][newC] = 2
        return island
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == 1:
                self.res = max(self.res, bfs(row, col, set([(row, col)])))
    return self.res

[DragonFCL]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let max = 0;
    let count = 0;
    function dfs(row, col) {
        if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] === 0) {
            return 0;
        }
        grid[row][col] = 0;
        count = 1
        count += dfs(row+1, col)
        count += dfs(row-1, col)
        count += dfs(row, col+1)
        count += dfs(row, col-1)
        return count;
    }
    for(let i = 0; i < grid.length; i++) {
        for(let j = 0; j < grid[0].length; j++){
            if(grid[i][j] === 1) {
                max = Math.max(max, dfs(i, j))
            }
        }
    }
    return max;
};

[Diana21170648]

思路

深度优先遍历

py代码

# 生成一个4行3列的包含 0 和 1 的非空二维数组 grid
grid = [[1, 1, 0],
        [1, 0, 1],
        [0, 1, 1],
        [1, 0, 0]]

# 定义DFS函数，用于搜索岛屿面积
def dfs(grid, i, j):
    # 判断当前位置是否越界或者已经搜索过
    if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
        return 0
    # 将当前位置标记为已搜索
    grid[i][j] = 0
    # 继续搜索上下左右四个方向
    area = 1
    area += dfs(grid, i-1, j)
    area += dfs(grid, i+1, j)
    area += dfs(grid, i, j-1)
    area += dfs(grid, i, j+1)
    return area

# 遍历整个二维数组，找到最大的岛屿面积
max_area = 0
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == 1:
            area = dfs(grid, i, j)
            max_area = max(max_area, area)

# 输出最大的岛屿面积
print(max_area)

**复杂度分析**
- 时间复杂度：O(r*c)
- 空间复杂度：O(r*c)

[kangliqi1]

class Solution { public int maxAreaOfIsland(int[][] grid) { boolean[][] seen = new boolean[grid.length][grid[0].length]; int[] dr = new int[]{1, -1, 0, 0}; int[] dc = new int[]{0, 0, 1, -1};

int ans = 0;
for (int r0 = 0; r0 < grid.length; r0++) {
    for (int c0 = 0; c0 < grid[0].length; c0++) {
        if (grid[r0][c0] == 1 && !seen[r0][c0]) {
            int shape = 0;
            Stack<int[]> stack = new Stack();
            stack.push(new int[]{r0, c0});
            seen[r0][c0] = true;
            while (!stack.empty()) {
                int[] node = stack.pop();
                int r = node[0], c = node[1];
                shape++;
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (0 <= nr && nr < grid.length &&
                            0 <= nc && nc < grid[0].length &&
                            grid[nr][nc] == 1 && !seen[nr][nc]) {
                        stack.push(new int[]{nr, nc});
                        seen[nr][nc] = true;
                    }
                }
            }
            ans = Math.max(ans, shape);
        }
    }
}
return ans;

} }

[RestlessBreeze]

code

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])

        def dfs(m,n):
            if m<0 or m>=row or n<0 or n>=col or grid[m][n]!=1:
                return 0
            cnt = 1
            grid[m][n]=0
            cnt +=dfs(m-1,n)+dfs(m+1,n)+dfs(m,n-1)+dfs(m,n+1)
            return cnt
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j]==1:
                    res = max(res,dfs(i,j))
        return res;

[jmaStella]

思路

dfs， 不用visited来track，直接修改grid

代码

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

    public int dfs(int[][] grid, int i, int j){
        if(grid[i][j] == 0){
            return 0;
        }
        int result = 1;
        grid[i][j] = 0;
        if(i-1 >=0){
            result+= dfs(grid, i-1, j);
        }
        if(i+1 <grid.length){
            result+= dfs(grid,i+1, j);
        }
        if(j-1 >=0){
            result+= dfs(grid,i, j-1);
        }
        if(j+1 <grid[0].length){
            result+= dfs(grid,i, j+1);
        }

        return result;
    }
}

复杂度

时间 O(N) N=number of element in grid 空间 O(N)

[Zoeyzyzyzy]

class Solution {
    public int dfs(int i, int j, int[][] grid){
        grid[i][j]=2;
        int c = 1;
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for(int[] d : directions){
            int new_x = i+d[0];
            int new_y = j+d[1];
            if(new_x>=0 && new_x<grid.length && new_y>=0 && new_y<grid[0].length && grid[new_x][new_y]==1){
                c+=dfs(new_x, new_y, grid);
            }
        }
        return c;
    }
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j]==1){
                    int area = dfs(i, j, grid);
                    max = Math.max(max,area);
                }
            }
        }
        return max;
    }
}

[X1AOX1A]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m == 0: return 0
        n = len(grid[0])
        ans = 0
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n: return 0
            if grid[i][j] == 0: return 0
            grid[i][j] = 0
            top = dfs(i + 1, j)
            bottom = dfs(i - 1, j)
            left = dfs(i, j - 1)
            right = dfs(i, j + 1)
            return 1 + sum([top, bottom, left, right])
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j))
        return ans

[JasonQiu]

• BFS

  class Solution:
  def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
      islands = []
      def search(x, y):
          for i in range(len(islands)):
              print(i, islands[i])
              if (x, y) in islands[i]:
                  print((x, y), "in island", i)
                  return i
      queue = [[0, 0]]
      while queue:
          [x, y] = queue.pop(0)
          if grid[x][y] == 1:
              if x > 0 and grid[x - 1][y] == 1:
                  islands[search(x - 1, y)].add((x, y))
              elif y > 0 and grid[x][y - 1] == 1:
                  islands[search(x, y - 1)].add((x, y))
              elif x < len(grid[0]) - 1 and grid[x + 1][y] == 1:
                  islands[search(x + 1, y)].add((x, y))
              elif y < len(grid) - 1 and grid[x][y + 1] == 1:
                  islands[search(x, y + 1)].add((x, y))
              else:
                  islands.append(set([(x,y)]))
          elif grid[x][y] == 0:
              if x < len(grid[0]) - 1:
                  queue.append([x + 1, y])
              if y < len(grid) - 1:
                  queue.append([x, y + 1])
          grid[x][y] = -1
      max_area = 0
      for i in range(len(islands)):
          if len(islands[i]) > max_area:
              max_area = len(islands[i])
      return max_area

[snmyj]

class Solution {
public:
    int dfs(vector<vector<int>>& grid,int i,int j){
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size())
            return 0;
        if (grid[i][j] != 1)
            return 0;
        grid[i][j] = 2;
        int temp = 1;
        int dx[4] = {-1,0,1,0};
        int dy[4] = {0,1,0,-1};
        for (int k = 0;k < 4;k++){
            temp += dfs(grid,i + dx[k], j + dy[k]);
        }
        return temp;

    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {

        int res = 0;
        for (int i = 0; i < grid.size();i ++)
            for (int j = 0;j < grid[0].size();j++)
                if (grid[i][j] == 1)
                    res = max(res,dfs(grid,i,j));
        return res;
    }
};

[Lydia61]

695. 岛屿的最大面积

思路

DFS

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m == 0: return 0
        n = len(grid[0])
        ans = 0
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n: return 0
            if grid[i][j] == 0: return 0
            grid[i][j] = 0
            top = dfs(i + 1, j)
            bottom = dfs(i - 1, j)
            left = dfs(i, j - 1)
            right = dfs(i, j + 1)
            return 1 + sum([top, bottom, left, right])
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j))
        return ans

[lp1506947671]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m == 0: return 0
        n = len(grid[0])
        ans = 0
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n: return 0
            if grid[i][j] == 0: return 0
            grid[i][j] = 0
            top = dfs(i + 1, j)
            bottom = dfs(i - 1, j)
            left = dfs(i, j - 1)
            right = dfs(i, j + 1)
            return 1 + sum([top, bottom, left, right])
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j))
        return ans

复杂度分析

• 时间复杂度：O(m*n)
• 空间复杂度：O(m*n)

[Fuku-L]

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for (int i = 0; i != grid.length; ++i) {
            for (int j = 0; j != grid[0].length; ++j) {
                ans = Math.max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }

    public int dfs(int[][] grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.length || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
            return 0;
        }
        grid[cur_i][cur_j] = 0;
        int[] di = {0, 0, 1, -1};
        int[] dj = {1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(MxN)
• 空间复杂度：O(MxN)

[jmaStella]

思路

DFS time out，brute force 方法不行 用BFS，从island开始 (starting with 1's) Use step to keep track

代码

public int maxDistance(int[][] grid) {
    //BFS, iterate starting 1's
    Queue<int[]> queue = new LinkedList<>();
    for(int i=0; i<grid.length; i++){
        for(int j=0; j<grid[0].length; j++){
            if(grid[i][j] == 1){
                queue.offer(new int[]{i, j});

            }
        }
    }
    if(queue.size() == 0 || queue.size() == grid.length * grid[0].length){
        return -1;
    }
    int result = -1;
    while(!queue.isEmpty()){
        int size = queue.size();

        for(int i=0; i<size; i++){
            int[] index = queue.poll();
            int x = index[0];
            int y = index[1];

            if(x+1<grid.length && grid[x+1][y] == 0){
                grid[x+1][y] = 1;
                queue.offer(new int[]{x+1, y});
            } 
            if(x-1>=0 && grid[x-1][y] == 0){
                grid[x-1][y] = 1;
                queue.offer(new int[]{x-1, y});
            } 
            if(y+1<grid[0].length && grid[x][y+1] == 0){
                grid[x][y+1] = 1;
                queue.offer(new int[]{x, y+1});
            } 
            if(y-1>=0 && grid[x][y-1] == 0){
                grid[x][y-1] = 1;
                queue.offer(new int[]{x, y-1});
            } 
        }
        result+=1;
    }
    return result;
}

复杂度

时间 O(NM) N grid长度，M grid宽度 空间 O(NM) N grid长度，M grid宽度

[chanceyliu]

代码

function maxAreaOfIsland(grid: number[][]): number {
  let row = grid.length;
  let col = grid[0].length;
  function dfs(x, y) {
    //越界判断 当grid[x][y] === 0时 直接返回
    if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] === 0) return 0;
    grid[x][y] = 0; //当grid[x][y] === 1时，将当前单元格置为0
    let ans = 1,
      dx = [-1, 1, 0, 0],
      dy = [0, 0, 1, -1]; //方向数组
    for (let i = 0; i < dx.length; i++) {
      //上下左右不断递归，计算每个岛屿的大小
      ans += dfs(x + dx[i], y + dy[i]);
    }
    return ans;
  }
  let res = 0;
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      res = Math.max(res, dfs(i, j)); //循环网格 更新最大岛屿
    }
  }
  return res;
};