What is the recommended approach for Max Area of Island?

DFS is preferred for grid traversal in this problem, as it efficiently counts connected 1's while matching the array plus DFS pattern.

Can BFS be used instead of DFS?

Yes, BFS works by exploring neighbors iteratively, avoiding recursion depth limits while producing the same maximum area result.

What if the grid has no land cells?

The function should return 0, since no islands exist, ensuring proper handling of empty or water-only grids.

How does union-find compare to DFS/BFS here?

Union-find can merge connected cells into sets and track maximum sizes, but it uses extra memory and may be overkill for small grids.

What are common mistakes in this problem pattern?

Including diagonals, missing edge checks, or failing to mark visited cells are typical errors when solving array plus DFS grid problems.

#695

Medium

auto_awesome图·搜索

LeetCode 题解工作台

岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0 （代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 gri…

数组深度优先搜索广度优先搜索并查集矩阵

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

lightbulb

解题思路

方法一：DFS

我们可以遍历每一个格子 $(i, j)$ ，从每个格子开始进行深度优先搜索，如果搜索到的格子是陆地，就将当前格子标记为已访问，并且继续搜索上、下、左、右四个方向的格子。搜索结束后，计算标记的陆地的数量，即为岛屿的面积。我们找出最大的岛屿面积即为答案。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是二维数组的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            if grid[i][j] == 0:
                return 0
            ans = 1
            grid[i][j] = 0
            dirs = (-1, 0, 1, 0, -1)
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n:
                    ans += dfs(x, y)
            return ans

        m, n = len(grid), len(grid[0])
        return max(dfs(i, j) for i in range(m) for j in range(n))

speed

复杂度分析

指标	值
时间	complexity is O(R _C) because each cell is visited once in DFS/BFS. Space complexity is O(R_ C) in the worst case due to recursion stack or queue for DFS/BFS or storage arrays for union-find.
空间	O(R*C)

psychology

面试官常问的追问

外企场景

question_mark
Looking for DFS traversal and marking visited cells correctly.
question_mark
Ensuring you handle edge boundaries without out-of-bounds errors.
question_mark
Tracking maximum area dynamically while traversing each island.

warning

常见陷阱

外企场景

error
Counting diagonally connected 1's incorrectly as part of an island.
error
Failing to mark visited cells, leading to overcounting areas.
error
Stack overflow on large grids when using naive DFS recursion.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the number of islands instead of the largest area.
arrow_right_alt
Find the largest island allowing diagonal connectivity.
arrow_right_alt
Determine the perimeter of the largest island rather than area.

help

常见问题

外企场景

继续练习

#778 水位上升的泳池中游泳 #827 最大人工岛 #959 由斜杠划分区域