岛屿的最大面积

怎样从“grid 求最大岛屿面积。”推导出 网格 DFS · 最大面积，并证明每次状态变化都不会漏掉答案？

中心结论：DFS 计数连通 1 个数,更新 max。

给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

在本站主例中，grid 求最大岛屿面积。

算法最终需要得到或观察：最大面积。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 DFS 面积、max。
3. 3转移每一步按照 DFS 计数连通 1 个数,更新 max。
4. 4收尾读取 最大面积。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：DFS 面积、max。

给出一个地图，要求计算上面岛屿的面积。注意岛屿的定义是四周都是海(为 0 的点)，如果土地(为 1 的点)靠在地图边缘，不能算是岛屿。 这一题和第 200 题，第 1254 题解题思路是一致的。DPS 深搜。这不过这一题需要多处理 2 件事情，一个是注意靠边缘的岛屿不能计算在内，二是动态维护岛屿的最大面积。

DFS 计数连通 1 个数,更新 max。

执行过程中持续维护：DFS 面积、max。

正确性依赖以下不变量：与 200 同框架,累加面积。

面试时可以压缩为：DFS flood fill 计数 O(mn)。

落到当前题，执行机制可以压缩为：DFS 计数连通 1 个数,更新 max。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入grid 求最大岛屿面积。 因为：DFS 计数连通 1 个数,更新 max。
2. 2扫描网格,遇 '1' 启动 DFS双重循环找未访问陆地。 因为：每个连通块只计数一次。
3. 3发现新岛屿,起点 (0,2)从该陆地 DFS 标记整块。 因为：沉岛避免重复计数。
4. 4该连通块已全部标记继续扫描。 因为：O(mn) 每个格最多访问一次。
5. 5发现新岛屿,起点 (0,7)从该陆地 DFS 标记整块。 因为：沉岛避免重复计数。
6. 6该连通块已全部标记继续扫描。 因为：O(mn) 每个格最多访问一次。
7. 7岛屿总数 2网格扫描结束。 因为：DFS/BFS 连通分量计数。
8. 8收尾与复杂度最大面积。 因为：时间 O(n) · 空间 O(1)。DFS 计数连通 1 个数,更新 max。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

var dir = [][]int{
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
}

func maxAreaOfIsland(grid [][]int) int {
	res := 0
	for i, row := range grid {
		for j, col := range row {
			if col == 0 {
				continue
			}
			area := areaOfIsland(grid, i, j)
			if area > res {
				res = area
			}
		}
	}
	return res
}

func isInGrid(grid [][]int, x, y int) bool {
	return x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0])
}

func areaOfIsland(grid [][]int, x, y int) int {
	if !isInGrid(grid, x, y) || grid[x][y] == 0 {
		return 0
	}
	grid[x][y] = 0
	total := 1
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		total += areaOfIsland(grid, nx, ny)
	}
	return total
}

func main() {
    // 1. 主例
    //    输入：mode="islands", 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"]]
    //    期望：最大面积。
    //
    // 2. 失败 / 未命中
    //    检查：沉岛时累加计数。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC200 岛屿数；LC733 填色
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意grid 求最大岛屿面积。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化DFS 计数连通 1 个数,更新 max。
4. 4证明与 200 同框架,累加面积。
5. 5复杂度时间 O(n)，空间 O(1)