【Day 50 】2024-10-03 - 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

[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位列数

[Fightforcoding]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        def bfs(i,j):
            #queue = deque([(i,j)])
            queue = deque()
            queue.append([i,j])
            grid[i][j] = 0
            area = 0
            while queue:
                x, y = queue.popleft()
                area += 1
                for dx, dy in [(1,0),(-1,0),(0, 1),(0, -1)]:
                    nx, ny = x + dx, y+dy
                    if 0<= nx < rows and 0<= ny <cols and grid[nx][ny] == 1:
                        queue.append((nx,ny))
                        grid[nx][ny] = 0
            return area
        max_area = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    max_area = max(max_area, bfs(i,j))
        return max_area

Time: O(m*n)

SpaceO(m*n)