华为 OD 训练营 · 题解精讲
LeetCode695、岛屿的最大面积
LeetCode695、岛屿的最大面积 视频地址：https://uha.xet.tech/s/4iPP5q
题目描述
给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。 岛屿的面积是岛上值为 1 的单元格的数目。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1： JPaxbLaHmoyie1xQZ0Tc7WNQnxd.jpg
输入： 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
题目解析
解题思路
本题要求计算二维网格中所有岛屿的最大面积，即连通块中 1 的个数最大值。参考代码采用深度优先搜索（DFS） 遍历每个连通块，统计其面积并更新最大值。
核心思想：遍历整个网格，每当遇到一个未被访问过的陆地单元格（值为 1），就以此点为起点进行 DFS，将整个连通块中所有陆地标记为已访问，并累计面积。遍历结束后取所有连通块面积的最大值。
数据结构：
- 使用与网格同大小的布尔矩阵
checkList记录每个单元格是否被访问过。 - 方向数组
DERICTIONS表示上下左右四个移动方向。
关键步骤
1. 初始化：获取网格尺寸 self.x、self.y，创建 checkList 全为 False，答案 ans = 0。 2. 双重循环遍历网格：
- 若当前格子是陆地（
grid[i][j] == 1）且未被访问（checkList[i][j] == False）： - 重置
self.area = 0。 - 调用
DFS(grid, i, j, checkList)进行深度优先搜索。 - 更新
ans = max(ans, self.area)。
3. DFS 函数：
- 标记当前点
(i,j)为已访问，面积self.area += 1。 - 遍历四个方向，对满足条件的邻点递归调用 DFS。
DFS 展开示意图（以 3×3 全 1 网格为例）：
初始 (0,0) 标记 → 面积+1
→ 右 (0,1) 标记 → 面积+1
→ 右 (0,2) 标记 → 面积+1
→ 下 (1,1) 标记 → 面积+1
→ 下 (2,1) 标记 → 面积+1
→ 左 (1,0) 标记 → 面积+1
→ 下 (2,0) 标记 → 面积+1
→ 右 (2,2) 标记 → 面积+1
最终面积 = 9复杂度分析
- 时间复杂度：O(m × n)，其中 m、n 为网格的行数和列数。每个单元格最多被访问一次（DFS 遍历时标记为已访问）。
- 空间复杂度：O(m × n)，主要来自
checkList数组和递归调用栈的深度（最坏情况下整个网格为一片陆地，递归深度为 m×n）。
参考代码
DFS解法
# 题目：LC695. 岛屿的最大面积
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问
# 初始化上下左右四个方向的数组
DERICTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
class Solution:
# 构建DFS函数
def DFS(self, grid, i, j, checkList):
# 将该点标记为已经检查过
checkList[i][j] = True
# 面积增大
self.area += 1
# 遍历上下左右四个方向的邻点坐标
for dx, dy in DERICTIONS:
next_i, next_j = i + dx, j + dy
# 若近邻点满足三个条件：
# 1.没有越界 2. 近邻点尚未被检查过 3.近邻点也为陆地
if ((0 <= next_i < self.x and 0 <= next_j < self.y) and checkList[next_i][next_j] == False
and grid[next_i][next_j] == 1):
# 对近邻点(ni, nj)进行DFS搜索
self.DFS(grid, next_i, next_j, checkList)
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
self.x = len(grid) # 获得网格长
self.y = len(grid[0]) # 获得网格宽
ans = 0 # 初始化答案为0
# 初始化数组checkList用于DFS遍历过程中的检查
# 0表示尚未访问，1表示已经访问
checkList = [[False] * self.y for _ in range(self.x)]
# 对整个grid二维数组进行双重循环遍历
for i in range(self.x):
for j in range(self.y):
# 若该点为陆地且还没有进行过搜寻
if grid[i][j] == 1 and checkList[i][j] == False:
# 在每一次DFS之前，先初始化面积为0
self.area = 0
# 可以进行DFS
self.DFS(grid, i, j, checkList)
# 做完DFS，更新ans
ans = max(ans, self.area)
return ans
BFS解法
# 题目：LC695. 岛屿的最大面积
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问
# 初始化上下左右四个方向的数组
DIRECTIONS = [(0,1), (1,0), (0,-1), (-1,0)]
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
x_len, y_len = len(grid), len(grid[0]) # 获得网格长宽
ans = 0 # 初始化陆地数目为0
# 初始化和grid一样大小的二维数组checkList用于DFS遍历过程中的检查
checkList = [[0] * y_len for _ in range(x_len)]
# 双重遍历grid数组
for i in range(x_len):
for j in range(y_len):
# 若该点为陆地且还没有进行过搜寻
# 找到了一个BFS搜索的起始位置(i,j)
if grid[i][j] == 1 and checkList[i][j] == 0:
# 对于该片连通块，构建一个队列，初始化包含该点
q = deque()
q.append((i,j))
# 修改checkList[i][j]为1，表示该点已经搜寻过
checkList[i][j] = 1
# 进行BFS之前，初始化该连通块的面积为0
area = 0
# 进行BFS，退出循环的条件是队列为空
while len(q) > 0:
# 弹出栈队头的点(x,y) 搜寻该点上下左右的近邻点
x, y = q.popleft()
area += 1
# 遍历(x,y)上下左右的四个方向的近邻点
for dx, dy in DIRECTIONS:
x_next, y_next = x+dx, y+dy
# 如果近邻点满足三个条件
if (0 <= x_next < x_len and 0 <= y_next < y_len and checkList[x_next][y_next] == 0
and grid[x_next][y_next] == 1):
# 对近邻点做两件事：
# 1. 入队 2. 标记为已检查过
q.append((x_next, y_next))
checkList[x_next][y_next] = 1
# 更新答案
ans = max(ans, area)
return ans