【Day 50 】2023-07-29 - 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

[Diana21170648]

思路

BFS

代码

from collections import deque
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m=len(grid)
        ans=0
        n=len(grid[0])
        fangxiang=[(1,0),(-1,0),(0,1),(0,-1)]#表示上下左右
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:#如果当前是陆地，开始bfs
                    queue=deque([(i,j)])#当做元组添加进去
                    grid[i][j]=0#标记为已访问，下一步开始岛屿面积加一
                    area=1

                    while queue:#队列不为空，就证明bfs还没有遍历结束
                        x,y=queue.popleft()
                        for fxx,fxy in fangxiang:
                            newx,newy=x+fxx,y+fxy
                            if 0<=newx<m and 0<=newy<n and grid[newx][newy]==1:
                                queue.append((newx,newy))
                                grid[newx][newy]=0
                                area+=1
                    ans=max(ans,area)
        return ans

复杂度分析

• 时间复杂度：O(M*N)
• 空间复杂度：O(M*N)

[zhaoygcq]

思路

通过dfs找出所有相连的格子，并记录其面积和；最终取最大值。 通过染色法实现对值为1的格子的查找。

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
  let area = 0;
  let m = grid.length, n = grid[0].length;
  for(let i = 0; i < m; i++) {
    for(let j = 0; j < n; j++) {
      if(grid[i][j] == 1) {
        let temp = dfs(grid, i, j);
        temp >= area && (area = temp);
      }
    }
  }

  return area;

  function dfs(grid, i, j) {
    let temp = 0;
    if(i < 0 || i >= m || j < 0 || j >= n) {
        return temp;
    }
    if(grid[i][j] == 1) {
        temp += 1;
        grid[i][j] = 2;
        temp += dfs(grid, i - 1, j);
        temp += dfs(grid, i + 1, j);
        temp += dfs(grid, i, j - 1);
        temp += dfs(grid, i, j + 1);
    }
    return temp;
  }
};

复杂度分析

• 时间复杂度：O(MN)，其中 N 为数组行数的长度， M为数组列数。
• 空间复杂度：O(1)

[catkathy]

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

        def dfs(x, y):
            if not (0 <= x < row and 0 <= y < col):
                return 0
            if grid[x][y] == 1:
                grid[x][y] = 0
                return 1 + dfs(x-1, y) + dfs(x, y-1) + dfs(x+1, y) + dfs(x, y+1)
            return 0

        for m in range(row):
            for n in range(col):
                if grid[m][n] == 1:
                    res = max(dfs(m, n), res)
        return res

[Alexno1no2]

# 遍历二维数组，对于每块土地，去其前后左右找相邻土地，再去前后左右的土地找其前后左右的土地，直到周围没有土地
# 对于每一块已找过的土地，为避免重复计算，将其置为0
# 遍历所有的岛屿，然后取这些岛屿的最大面积res = max(res, dfs(i, j))

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j]:
                grid[i][j] = 0
                return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
            return 0

        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    res = max(res, dfs(i, j))
        return res

[liuajingliu]

解题思路

DFS

1. 从陆地出发，遍历该陆地所在的岛屿
   • 从隶属于该岛屿的某一块陆地出发，向四个方向递归地进行DFS
   • 每次递归对下标进行判断，以区域的边界作为递归边界
   • 将已访问过的陆地置为0，以保证每块陆地只访问一次
   • 递归地返回整块岛屿陆地面积
2. 找出所有岛屿的最大值

代码实现

javaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let x = grid.length;
    let y = grid[0].length;
    let max = 0;
    // 遍历二维数组
    for (let i = 0; i < x; i ++) {
       for (let j = 0; j < y; j ++) {
           if (grid[i][j] === 1) {
               max = Math.max(max, areaOfIsland(grid, i, j, x, y));
           }
       } 
    }
    return max;
};

var areaOfIsland = function(grid, i, j, x, y) {
    // 判断边界条件
    if(i < 0 || i >= x || j < 0 || j >= y || grid[i][j] === 0) {
        return 0
    }
    let ans = 1;
    // 将遍历过的岛屿标记为0
    grid[i][j] = 0;
    // 遍历岛屿四周
    ans += areaOfIsland(grid, i + 1, j, x, y);
    ans += areaOfIsland(grid, i - 1, j, x, y);
    ans += areaOfIsland(grid, i, j + 1, x, y);
    ans += areaOfIsland(grid, i, j - 1, x, y);
    return ans;
}

复杂度分析

• 时间复杂度 $O(R * C )$, 其中R为二维数组行数，C位列数
• 空间复杂度 $O(R * C )$, 其中R为二维数组行数，C位列数

[Beanza]

var maxAreaOfIsland = function(grid) { let x = grid.length; let y = grid[0].length; let max = 0; // 遍历二维数组 for (let i = 0; i < x; i ++) { for (let j = 0; j < y; j ++) { if (grid[i][j] === 1) { max = Math.max(max, areaOfIsland(grid, i, j, x, y)); } } } return max; };

var areaOfIsland = function(grid, i, j, x, y) { // 判断边界条件 if(i < 0 || i >= x || j < 0 || j >= y || grid[i][j] === 0) { return 0 } let ans = 1; // 将遍历过的岛屿标记为0 grid[i][j] = 0; // 遍历岛屿四周 ans += areaOfIsland(grid, i + 1, j, x, y); ans += areaOfIsland(grid, i - 1, j, x, y); ans += areaOfIsland(grid, i, j + 1, x, y); ans += areaOfIsland(grid, i, j - 1, x, y); return ans; }

[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;
    }
}

[yetfan]

代码

class Solution:
    def dfs(self, grid, cur_i, cur_j) -> int:
        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 [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            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

[snmyj]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        m,n = len(grid), 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

[HuiyingC]

class Solution(object):
    # dfs解法 time complexity: O(n*m) 所有的点都只算了一次

    def maxAreaOfIsland(self, grid):
        n, m = len(grid), len(grid[0])

        mx = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j]:
                    mx = max(mx, self.dfs(grid, i, j))
        return mx

    def dfs(self, grid, i, j):
        n, m = len(grid), len(grid[0])

        if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == 0:
            return 0

        grid[i][j] = 0
        return 1 + self.dfs(grid, i - 1, j) + self.dfs(grid, i + 1, j) + self.dfs(grid, i, j - 1) + self.dfs(grid, i, j + 1)