每日一道算法之--岛屿的最大面积

Word count: 1.3kReading time: 5 min

 2020/03/15   Share

岛屿的最大面积

力扣第695题:https://leetcode-cn.com/problems/max-area-of-island/

给定一个包含了一些 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)

DFS重在追求”专一”吧!一条道走到黑,我们想知道网格中每个连通形状的面积，然后取最大值。

二维数组中每一个位置都有可能是刀鱼最大面积的起点,所以每一个位置都要去作为起点去搜索
以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。递归到最深一层,然后判断是否符合要求,然后再层层往上回退。
为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0。这样我们就不会多次访问同一土地。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        rows = len(grid)
        cols = len(grid[0])
        max_area = 0
        for row in range(rows):
            for col in range(cols):
                max_area = max(self.dfs(row, col, rows, cols, grid), max_area)
        return max_area

    def dfs(self, row, col, rows, cols, grid):
        res = 0
        # 只有为1的时候才算岛屿
        if 0 <= row < rows and 0 <= col < cols and grid[row][col] != 0 :  
            # 搜索过的就置为0，防止重复搜索  
            grid[row][col] = 0  
            res = 1  
            for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                new_row, new_col = row + di, col + dj
                res += self.dfs(new_row, new_col, rows, cols, grid)
        return res

DFS也可以用栈来实现

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        rows = len(grid)
        cols = len(grid[0])
        max_area = 0
        for row in range(rows):
            for col in range(cols):
                stack = [(row, col)]
                res = 0
                while stack:
                    row, col = stack.pop()
                    if 0 <= row < rows and 0 <= col < cols and grid[row][col] != 0 :
                        grid[row][col] = 0
                        res += 1
                        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                            new_row, new_col = row + di, col + dj
                            stack.append((new_row, new_col))
                max_area = max(max_area, res)
        return max_area

1.1 复杂度分析

时间复杂度： 我们访问每个网格最多一次。所以时间复杂度为$$O(R * C)$$。其中 R 是给定网格中的行数，C 是列数。

空间复杂度：递归的深度最大可能是整个网格的大小，因此最大可能使用 $$O(R * C) $$的栈空间,所以空间复杂度为$$O(R * C)$$

2. 广度优先搜索(BFS)

顾名思义，广度优先搜索追求的是”覆盖面积”。其实只要将深度优先搜索中的栈换成队列，就可以实现广度优先搜索。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        rows = len(grid)
        cols = len(grid[0])
        max_area = 0
        for i in range(rows):
            for j in range(cols):
                queue = collections.deque([(i, j)])
                res = 0
                while queue:
                    row, col = queue.popleft()
                    if 0 <= row < rows and 0 <= col < cols and grid[row][col] != 0 :
                        grid[row][col] = 0
                        res += 1
                        for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                            new_row, new_col = row + di, col + dj
                            queue.append((new_row, new_col))
                max_area = max(max_area, res)
        return max_area

2.1 复杂度分析

时间复杂度： 我们访问每个网格最多一次。所以时间复杂度为$$O(R * C)$$。其中 R 是给定网格中的行数，C 是列数。

空间复杂度：递归的深度最大可能是整个网格的大小，因此最大可能使用 $$O(R * C) $$的栈空间,所以空间复杂度为$$O(R * C)$$

##总结
深度优先搜索和栈有关,广度优先搜索和队列有关.

##python特别注意的一点
如果仔细看代码,你会发现我在用栈实现的时候和用队列实现的时候,有一句代码不一样:

用栈实现的;
for row in range(rows):
    for col in range(cols):
        stack = [(row, col)]

用队列实现的:
for i in range(rows):
    for j in range(cols):
        queue = collections.deque([(i, j)])