1. 题目背景与核心挑战力扣695题岛屿的最大面积是经典的二维矩阵遍历问题。给定一个由0水域和1陆地组成的二维网格我们需要计算其中连通岛屿的最大面积。这里的连通指的是水平或垂直相邻的1组成的区域。这个问题看似简单但蕴含着几个关键挑战如何高效地遍历二维矩阵如何避免重复计算已访问的区域如何设计简洁的搜索策略如何处理边界条件2. 算法思路解析2.1 深度优先搜索(DFS)方案DFS是解决这类连通性问题的自然选择。基本思路是遍历矩阵中的每个单元格当遇到1时启动DFS搜索在DFS过程中将访问过的1标记为0避免重复计算统计当前岛屿的面积并与最大值比较def maxAreaOfIsland(grid): max_area 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or r rows or c 0 or c cols or grid[r][c] 0: return 0 grid[r][c] 0 # 标记为已访问 return 1 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1: max_area max(max_area, dfs(r, c)) return max_area2.2 广度优先搜索(BFS)方案BFS同样适用于此问题使用队列实现from collections import deque def maxAreaOfIsland(grid): max_area 0 rows, cols len(grid), len(grid[0]) for r in range(rows): for c in range(cols): if grid[r][c] 1: queue deque([(r, c)]) grid[r][c] 0 current_area 1 while queue: x, y queue.popleft() for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 current_area 1 queue.append((nx, ny)) max_area max(max_area, current_area) return max_area3. 算法优化与变种3.1 空间复杂度优化原始方案修改了输入矩阵如果不允许修改输入可以使用额外的visited矩阵def maxAreaOfIsland(grid): max_area 0 rows, cols len(grid), len(grid[0]) visited [[False for _ in range(cols)] for _ in range(rows)] def dfs(r, c): if r 0 or r rows or c 0 or c cols or grid[r][c] 0 or visited[r][c]: return 0 visited[r][c] True return 1 dfs(r1, c) dfs(r-1, c) dfs(r, c1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] 1 and not visited[r][c]: max_area max(max_area, dfs(r, c)) return max_area3.2 并查集(Union-Find)方案虽然DFS/BFS更直观但并查集也是一种可行的解决方案class UnionFind: def __init__(self, grid): rows, cols len(grid), len(grid[0]) self.parent [i for i in range(rows * cols)] self.rank [0] * (rows * cols) self.size [grid[r][c] for r in range(rows) for c in range(cols)] def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root y_root: return if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root self.size[y_root] self.size[x_root] else: self.parent[y_root] x_root self.size[x_root] self.size[y_root] if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1 def maxAreaOfIsland(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(grid) for r in range(rows): for c in range(cols): if grid[r][c] 1: index r * cols c if r 0 and grid[r-1][c] 1: uf.union(index, (r-1)*cols c) if c 0 and grid[r][c-1] 1: uf.union(index, r*cols (c-1)) return max(uf.size) if uf.size else 04. 复杂度分析与比较算法时间复杂度空间复杂度适用场景DFSO(M×N)O(M×N)代码简洁递归深度可能成为问题BFSO(M×N)O(min(M,N))适合大规模网格避免递归栈溢出并查集O(M×N×α(M×N))O(M×N)需要动态维护连通性时更优其中M和N分别是网格的行数和列数α是反阿克曼函数增长极其缓慢。5. 常见错误与调试技巧5.1 边界条件处理常见错误包括忘记检查网格边界在DFS/BFS中重复访问同一单元格没有正确处理空输入的情况调试技巧打印访问过的单元格坐标使用小规模测试用例手动验证检查递归/循环终止条件5.2 性能优化建议对于大规模网格考虑使用迭代而非递归的DFS实现在BFS中使用双端队列(deque)而非列表(list)对于并行计算场景可以考虑分块处理6. 实际应用场景这类算法在实际中有广泛应用图像处理中的连通区域分析游戏开发中的地图生成与区域划分社交网络中的社群发现地理信息系统中的区域统计理解这类基础算法问题有助于解决更复杂的实际问题。例如可以扩展为计算多个岛屿的平均面积找出特定形状的岛屿动态更新岛屿实时处理网格变化