每日一题-15

题目描述

岛屿的最大面积
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为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。

解题思路

1.dfs遍历每个岛屿的上下左右的岛屿数，求最大值。主要注意边界问题，以及访问了一个岛屿之后需要将其修改成非1（也可以直接设置为0，但是设置成非1非0，防止可能需要恢复原grid数组），避免将一个岛屿重复计算。
2.深度优先+栈，广度优先
https://leetcode-cn.com/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        length = len(grid[0])
        high = len(grid)
        ans  = 0
        for i in range(high):
            for j in range(length):
                if grid[i][j]!=0:
                    ans = max(ans, self.dfs(i,j,grid))
        return ans

    def dfs(self, i, j, grid):
        if  i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]!=1:
            return 0

        grid[i][j] = 2

        num = 1

        op = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        for dx, dy in op:
            num+=self.dfs(i+dx, j+dy, grid)
        return num