【LeetCode】200. 岛屿数量 & 695. 岛屿的最大面积（高频题！！！经典 DFS 和 BFS 高频题 商汤、字节面试题）

一、岛屿数量

1.1. 题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。 示例 1:

输入:

[ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出: 1 示例 2: 输入: [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

1.2. 解题思路 & 代码

1.2.1. DFS 深度优先遍历

递归转化为迭代的话可以用栈，后进先出

我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0，这样可以避免两个 for 循环重复搜索。

最终岛屿的数量就是我们进行深度优先搜索的次数。

# 在开头加上 # import sys # python 默认递归深度不超过1000，做dfs会比C吃亏 # sys.setrecursionlimit(10000000)# 手动修改深度 class Solution: def dfs(self, grid, r, c): grid[r][c] = '0' # 每次某个岛屿计数以后，把该岛屿所有 1 都归 0，这样两个 for 循环 就不会重复遍历了 nr = len(grid) nc = len(grid[0]) for new_r, new_c in [[r-1,c],[r+1,c],[r, c-1],[r, c+1]]: if 0 <= new_r < nr and 0 <= new_c <nc and grid[new_r][new_c] == '1': self.dfs(grid, new_r, new_c) def numIslands(self, grid: List[List[str]]) -> int: nr = len(grid) # 行数 if nr == 0: return 0 nc = len(grid[0]) # 列数 num_land = 0 for r in range(nr): for c in range(nc): if grid[r][c] == '1': num_land += 1 self.dfs(grid, r, c) return num_land

复杂度分析

时间复杂度：$O(MN)$，其中 $M$ 和 $N$ 分别为行数和列数。

空间复杂度：$O(MN)$，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 $MN$。

1.2.2. BFS 广度优先遍历

广度优先用队列，先进先出

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。 class Solution: def numIslands(self, grid: List[List[str]]) -> int: nr = len(grid) if nr == 0: return 0 nc = len(grid[0]) num_land = 0 queue = [] # 队列，可用列表表示 for r in range(nr): for c in range(nc): if grid[r][c] == '1': num_land += 1 queue.append([r, c]) # 入队 # grid[r][c] = '0' # 这里标记已访问可有可无 while queue: row, col = queue.pop(0) #左边出队（先进先出） for i, j in [[row-1, col],[row+1, col],[row, col-1],[row, col+1]]: if 0 <= i < nr and 0 <= j < nc and grid[i][j] == '1': queue.append([i, j]) # 入队 grid[i][j] = '0' # 放入队列以后马上标记为已访问，即置零 return num_land

复杂度分析

时间复杂度：$O(MN)$，其中 $M$ 和 $N$ 分别为行数和列数。

空间复杂度：$O(min(M,N))$，在最坏情况下，整个网格均为陆地，队列的大小可以达到 $min(M,N)$。

####################################################################################################################################################################################################################################################################

二、岛屿面积

2.1. 题目描述

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

2.2. 解题思路 & 代码

2.2.1 DFS

算法

我们想知道网格中每个连通形状的面积，然后取最大值。如果我们在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0。这样我们就不会多次访问同一土地。 class Solution: def dfs(self, grid, cur_i, cur_j): if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: return 0 grid[cur_i][cur_j] = 0 ans = 1 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: next_i, next_j = cur_i + di, cur_j + dj ans += self.dfs(grid, next_i, next_j) return ans def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ans = 0 for i, l in enumerate(grid): for j, n in enumerate(l): ans = max(self.dfs(grid, i, j), ans) return ans

复杂度分析

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

空间复杂度：O(R∗C)，递归的深度最大可能是整个网格的大小，因此最大可能使用 O(R∗C) 的栈空间。

2.2.2 DFS + 栈

算法

我们可以用栈来实现深度优先搜索算法。这种方法本质与方法一相同，唯一的区别是：方法一通过函数的调用来表示接下来想要遍历哪些土地，让下一层函数来访问这些土地。而方法二把接下来想要遍历的土地放在栈里，然后在取出这些土地的时候访问它们。访问每一片土地时，我们将对围绕它四个方向进行探索，找到还未访问的土地，加入到栈 stack 中；另外，只要栈 stack 不为空，就说明我们还有土地待访问，那么就从栈中取出一个元素并访问。 class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ans = 0 for i, l in enumerate(grid): for j, n in enumerate(l): cur = 0 stack = [(i, j)] while stack: cur_i, cur_j = stack.pop() if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: continue cur += 1 grid[cur_i][cur_j] = 0 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: next_i, next_j = cur_i + di, cur_j + dj stack.append((next_i, next_j)) ans = max(ans, cur) return ans

复杂度分析

时间复杂度：O(R∗C)。其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。空间复杂度：O(R∗C)，栈中最多会存放所有的土地，土地的数量最多为 R∗C 块，因此使用的空间为 O(R∗C)。

2.2.3 BFS （队列）

算法

我们把方法二中的栈改为队列，每次从队首取出土地，并将接下来想要遍历的土地放在队尾，就实现了广度优先搜索算法。

class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ans = 0 n = len(grid) m = len(grid[0]) queue = [] for i in range(n): # 从某个坐标 [i, j] 进入搜索 for j in range(m): cur = 0 # 从 [i, j] 进入搜索的该岛屿的面积 queue.append([i, j]) # 入队 while queue: cur_i, cur_j = queue.pop(0) # 相当于 collections 的 queue 的 popleft() if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: continue # 不是需要探索的陆地，跳过该点 cur += 1 # 既然没有进入 if ，则说明这个点是正常的陆地，面积 + 1 grid[cur_i][cur_j] = 0 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: # 把四周的点都入队（典型的 BFS ） next_i, next_j = cur_i + di, cur_j + dj queue.append([next_i, next_j]) ans = max(ans, cur) return ans ######################### 下面的写法也可以 ########################### # class Solution: # def maxAreaOfIsland(self, grid: List[List[int]]) -> int: # ans = 0 # for i, l in enumerate(grid): # for j, n in enumerate(l): # cur = 0 # q = collections.deque([(i, j)]) # while q: # cur_i, cur_j = q.popleft() # if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: # continue # cur += 1 # grid[cur_i][cur_j] = 0 # for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: # next_i, next_j = cur_i + di, cur_j + dj # q.append((next_i, next_j)) # ans = max(ans, cur) # return ans

复杂度分析

时间复杂度：O(R∗C)。其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。空间复杂度：O(R∗C)，队列中最多会存放所有的土地，土地的数量最多为R∗C 块，因此使用的空间为 O(R∗C)。

参考：

LeetCode 200. 题解.LeetCode 695. 官方题解