【Day 50 】2024-05-27 - 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

[xy147]

js代码

var maxAreaOfIsland = function (grid) {
  let x = grid[0].length,
    y = grid.length;
  let res = 0;
  function dfs(i, j) {
    if (i >= y || j >= x || j < 0 || i < 0 || grid[i][j] != 1) return 0;
    grid[i][j] = -1;
    return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j - 1) + dfs(i, j + 1);
  }
  for (let i = 0; i < y; i++) {
    for (let j = 0; j < x; j++) {
      if (grid[i][j]) {
        res = Math.max(res, dfs(i, j));
      }
    }
  }
  return res;
};

复杂度分析

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

[rao-qianlin]

class Solution {
    int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        int m = grid.length, 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;
    }

    int dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return 0;
        }
        if (grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;

        return dfs(grid, i + 1, j)
            + dfs(grid, i, j + 1)
            + dfs(grid, i - 1, j)
            + dfs(grid, i, j - 1) + 1;
    }
}

[wwz223]

function maxAreaOfIsland(grid: number[][]): number {
    const row:number = grid.length,
        col:number = grid[0].length;

    let maxIsland:number = 0;

    interface IDfs {
        (i:number, j:number):number
    }

    const dfs:IDfs = (i, j) => {

        // 边界判断
        let iJudge:boolean = i < 0 || i >= row,
            jJudge:boolean = j < 0 || j >= col;

        if (iJudge || jJudge || grid[i][j] === 0) {
            // 不符合条件则 直接返回0
            return 0;
        }

        // 遍历过的节点置 0 防止多次计数
        grid[i][j] = 0;
        let cntIsland:number = 1;

        cntIsland += dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1);

        return cntIsland;
    }

    // 遍历地图(因遍历过后的节点都为0，不会重复遍历)，并取最大值
    for(let i:number = 0; i < row; i++) {
        for (let j:number = 0; j < col; j++) {
            maxIsland = Math.max(maxIsland, dfs(i,j));
        }
    }

    return maxIsland;

};

[franklinsworld666]

代码

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

        def dfs(x, y):
            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0:
                return 0
            grid[x][y] = 0  # Mark as visited by setting to 0
            return (1 +
                    dfs(x+1, y) +
                    dfs(x-1, y) +
                    dfs(x, y+1) +
                    dfs(x, y-1))

        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

[lxy1108]

python3代码

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

[GReyQT]

class Solution {
public:
    typedef pair<int, int> PII;
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    int bfs(vector<vector<int>>& grid, vector<vector<bool>>& st, int x, int y) {
        int area = 1;
        queue<PII> q;
        q.push({x, y});
        while (!q.empty()) {
            auto t = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int xi = t.first + dx[i];
                int yi = t.second + dy[i];

                if (xi < 0 || xi >= grid.size() || yi < 0 ||
                    yi >= grid[0].size()) {
                    continue;
                }

                if (!st[xi][yi] && grid[xi][yi] == 1) {
                    area++;
                    st[xi][yi] = true;
                    q.push({xi, yi});
                }
            }
        }
        return area;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        vector<vector<bool>> st =
            vector<vector<bool>>(n, vector<bool>(m, false));

        int cnt = 0;
        int max_area = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!st[i][j] && grid[i][j] == 1) {
                    st[i][j] = true;
                    cnt++;
                    int area = bfs(grid, st, i, j);
                    max_area = max(max_area, area);
                }
            }
        }
        if (cnt == 0)
            return 0;
        return max_area;
    }
};

[Dtjk]

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