岛屿的最大面积

难度: Medium

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[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：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

Submission

运行时间: 35 ms

内存: 16.6 MB

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
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    ans = max(ans, dfs(i, j))

        return ans

Explain

该题解采用深度优先搜索(DFS)的方法来解决问题。对于网格中的每个为1的点，以该点为起始进行DFS遍历，将遍历过的点置为0，并累加遍历的岛屿面积。在遍历过程中，递归地向上、下、左、右四个方向扩展，直到遇到边界或者遇到0为止。每次遍历后更新最大岛屿面积。遍历完整个网格后，即可得到最大的岛屿面积。

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

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

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j):
            # 边界条件：超出网格范围或当前位置为0
            if 0<=i<m and 0<=j<n and grid[i][j]:
                # 将当前位置置为0，避免重复访问
                grid[i][j] = 0
                # 递归访问上、下、左、右四个方向，累加岛屿面积
                return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
            return 0
        
        ans = 0
        for i in range(m):
            for j in range(n):
                # 对于每个为1的位置，进行DFS遍历
                if grid[i][j]:
                    ans = max(ans, dfs(i, j))

        return ans

Explore

在DFS函数中检查当前位置是否为1是必要的，因为这个检查确定了当前位置是否是岛屿的一部分（即是否为陆地）。如果当前位置为0，则表示是水域，不应继续进行DFS。此外，这个检查也防止了对已经访问过并标记为0的位置重复访问，从而避免了无限递归和错误的面积计算。

如果在递归调用dfs时不将访问过的1置为0，将导致算法重复访问同一个岛屿的部分。这种重复访问会造成无限递归，因为算法会不停地在已经访问过的岛屿部分之间循环。此外，它也会导致错误地计算岛屿的面积，因为同一块陆地会被多次计算。

在DFS中，遇到边界条件时返回0是一种常见的处理方式，用于标示已经到达不可继续探索的区域（如网格边界或水域）。这种处理方式在本题中是适用的，因为它简化了代码并防止了访问数组外的索引。然而，这种处理方式不一定适用于所有情况，具体依赖于问题的要求和边界的定义。在其他类型的DFS问题中，可能需要采取不同的边界处理策略。

函数maxAreaOfIsland中需要两层循环遍历整个网格是为了确保每个为1的点都被考虑作为岛屿的起始点进行DFS遍历。这样可以确保找到所有独立的岛屿，并计算出每个岛屿的面积。只有全面遍历整个网格，才能正确地计算出最大的岛屿面积。