LeetCode 695中等网格 DFS
岛屿的最大面积 图解题解
这道题到底在问什么
网格中 1 表示陆地，求最大岛屿面积。
- grid
- [[1,1,0,0],[1,1,0,1],[0,0,0,1]]
- 输出
- 4
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合网格 DFS。
- 4求最大岛屿面积——网格里相邻陆地连成一座岛，要找格子数最多的那座。办法：对每座岛 DFS 淹掉、边淹边数格子，记录见过的最大面积 best。
- 5从左上角扫，碰到第一格陆地 (0,0)。启动 DFS：把它淹掉(标记已访问)，本岛面积记 1。
- 6DFS 向上下左右找相邻陆地。(0,1) 是陆地，淹掉，本岛面积 + 1 = 2。
- 7沿着连通的陆地一路淹：(1,0)、(1,1) 也是这座岛的。全部淹完，这座岛共 4 格。
- 8DFS 返回，这座岛面积是 4。和已知最大比较：best 从 0 更新为 4。
- 9接着往后扫，碰到新的陆地 (1,3)。这是另一座岛，本岛面积从 1 重新数(best 仍记着 4)。
- 10这座岛只有 (1,3)、(2,3) 两格，面积 2。2 小于 4，best 保持 4 不变。
- 11整张网格扫完，所有岛都数过了。最大岛屿面积 = best = 4。关键：DFS 数一座岛的面积，外层循环取所有岛的最大。
- 14把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：数完一座岛不标记
✓ 对：DFS 时要把访问过的陆地淹掉
否则会重复统计
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def maxAreaOfIsland(self, grid):
m, n = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
return 0
grid[r][c] = 0 # 淹掉，避免重复数
return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)
best = 0
for r in range(m):
for c in range(n):
best = max(best, dfs(r, c)) # 每座岛取最大
return bestC++
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
best = max(best, dfs(grid, r, c));
return best;
}
int dfs(vector<vector<int>>& g, int r, int c) {
if (r < 0 || r >= (int)g.size() || c < 0 || c >= (int)g[0].size() || g[r][c] == 0) return 0;
g[r][c] = 0;
return 1 + dfs(g,r+1,c) + dfs(g,r-1,c) + dfs(g,r,c+1) + dfs(g,r,c-1);
}
};Java
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
best = Math.max(best, dfs(grid, r, c));
return best;
}
int dfs(int[][] g, int r, int c) {
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] == 0) return 0;
g[r][c] = 0;
return 1 + dfs(g,r+1,c) + dfs(g,r-1,c) + dfs(g,r,c+1) + dfs(g,r,c-1);
}
}套路模板 · 网格 DFS（数面积）
def dfs(r, c):
if 越界 or grid[r][c] != 目标:
return 0 # 边界/非目标 → 贡献 0
grid[r][c] = 已访问标记 # 淹掉，避免重复
return 1 + dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1)
# 外层：for 每个格子: best = max(best, dfs(r,c))int dfs(Grid& g, int r, int c) {
if (越界 || g[r][c] != 目标) return 0;
g[r][c] = 已访问;
return 1 + dfs(g,r+1,c)+dfs(g,r-1,c)+dfs(g,r,c+1)+dfs(g,r,c-1);
}
// 外层: for 每格 best = max(best, dfs(g,r,c));int dfs(int[][] g, int r, int c) {
if (越界 || g[r][c] != 目标) return 0;
g[r][c] = 已访问;
return 1 + dfs(g,r+1,c)+dfs(g,r-1,c)+dfs(g,r,c+1)+dfs(g,r,c-1);
}
// 外层: for 每格 best = Math.max(best, dfs(g,r,c));复杂度
时间复杂度
O(mn)
每个格子最多被访问一次(淹掉后不再进)
空间复杂度
O(mn)
DFS 递归栈，最坏 O(m·n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 岛屿的最大面积 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和「岛屿数量 LC200」的区别？+
LC200 数岛个数(每岛 +1)；本题数每岛面积取最大。DFS 框架一样，把「+1」换成「累加面积取 max」。
为什么改 0 而不用 visited？+
改 0 省一个数组、和「淹岛」语义一致；用 visited 则不破坏原网格，二选一。
复杂度？+
O(m·n) 每格访问一次。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。