某外包吐槽：本人鹅厂外包，喜欢上了正式员小姐姐，昨天约她晚上一起吃饭，话里话外意思是让我找份正经工作，不想跟我浪费时间~

嗨，大家好！今天我们来聊聊一个经典的算法题：岛屿的最大面积。

这道题目常常出现在面试中，考察的是你对深度优先搜索（DFS）或者广度优先搜索（BFS）的理解，也能考察你对二维数组的操作熟练度。好吧，先不说那些艰深的名词，我们还是从代码和实际操作的角度出发，看看如何解决这个问题。

问题分析

题目大致是这样的：给定一个由 1 和 0 组成的二维网格，其中 1 代表陆地，0 代表水域。一个岛屿是由相连的陆地组成的，岛屿的连通性是八方向的，即上下左右以及四个对角线方向都可以连通。你的任务是找出最大的岛屿面积。

简单来说，就是要找出最多的连通陆地块数。

思路与解法

第一步是遍历整个二维网格，发现一个陆地块（即值为1），然后通过深度优先搜索（DFS）或者广度优先搜索（BFS）来“扫荡”这个岛屿，标记已经访问过的陆地块，并计算面积，最后更新最大面积。

DFS和BFS的区别就在于，DFS是递归的，BFS是用队列逐层展开。两者在此题中都能解决，但DFS的实现比较简单，所以我们这次使用DFS。

代码实现

好啦，下面我们来写点代码，解决这个问题：

def maxAreaOfIsland(grid):
    if not grid:
        return 0
    def dfs(i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
            return 0
        grid[i][j] = 0  # 标记为已访问
        area = 1  # 当前陆地块的面积
        # 八个方向的递归搜索
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        for di, dj in directions:
            area += dfs(i + di, j + dj)
        return area
    max_area = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:  # 找到一个新的岛屿
                max_area = max(max_area, dfs(i, j))  # 更新最大岛屿面积
    return max_area

代码解读

1. dfs函数：我们定义了一个递归的dfs函数，它会在网格中探索从某个陆地块开始的所有连通的陆地块。每次递归时，都会把访问过的陆地块标记为0（即水域），避免重复计算。

2. 八方向搜索：我们通过directions数组来存储八个方向，确保可以同时搜索上下左右及四个对角线方向。

3. 最大面积计算：每当我们从一个新的岛屿开始搜索时，就用dfs计算它的面积，并用max_area来记录目前找到的最大岛屿面积。

时间与空间复杂度

• 时间复杂度：O(m * n)，其中 m 是行数，n 是列数。我们遍历每一个网格单元一次，对于每个陆地块执行一次dfs。
• 空间复杂度：O(m * n)，最坏情况下，递归栈的最大深度会达到 m * n（也就是每个陆地块都在一个岛屿中）。

额外考虑

1. 性能优化：如果岛屿很大，递归深度可能会达到Python的最大递归深度（默认是1000）。为了避免这个问题，可以将递归改为迭代的BFS。

2. 边界条件：输入网格为空时，我们需要提前返回0。

代码优化（BFS）

如果你不喜欢递归，也可以用队列实现BFS：

from collections import deque
def maxAreaOfIsland(grid):
    if not grid:
        return 0
    def bfs(i, j):
        area = 0
        queue = deque([(i, j)])
        grid[i][j] = 0  # 标记为已访问
        while queue:
            x, y = queue.popleft()
            area += 1
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 1:
                    grid[nx][ny] = 0  # 标记为已访问
                    queue.append((nx, ny))
        return area
    max_area = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                max_area = max(max_area, bfs(i, j))
    return max_area

最后总结

岛屿的最大面积题目看起来简单，其实细节不少，尤其是在如何遍历和处理每个岛屿时，递归和迭代的选择都会影响代码的效率和可读性。如果你面试时遇到类似问题，可以灵活运用DFS或者BFS，尽量避免写出过于复杂的代码，保持清晰和简洁。

对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。

虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。