LeetCode 695中等网格 DFS
岛屿的最大面积 图解题解
这道题到底在问什么
在 4×5 矩阵里，1=陆地 0=水。相邻（上下左右）的陆地属于同一座岛，求最大岛的面积（格子数）。没有陆地则为 0。
- 输入
- grid=[[1,1,0,1,1],[1,0,0,1,0],[0,0,1,1,0],[1,1,1,0,1]]
- 输出
- 8
最优解：一步一步想明白
- 3关键两件事：① 每数一格就标记防重复；② 一座岛数完，用它的面积刷新最大值。
- 4开始逐行逐列扫格子，蓝色是水、浅蓝是还没数到的陆地。碰到没数过的陆地就启动一次 DFS。
- 5扫到 (0,0) 是没数过的陆地 → 发现第 1 座岛，从这里开始 DFS 把它整片数出来。
- 6走到陆地 (0,0)：数过它，当前这座岛面积 = 1，刷新了见过的最大面积 → 1。
- 7走到陆地 (0,1)：数过它，当前这座岛面积 = 2，刷新了见过的最大面积 → 2。
- 8走到陆地 (1,0)：数过它，当前这座岛面积 = 3，刷新了见过的最大面积 → 3。
- 9第 1 座岛数完，面积 = 3。它是目前见过最大的，最大面积保持 3。归档（变绿），继续往后扫。
- 10扫到 (0,3) 是没数过的陆地 → 发现第 2 座岛，从这里开始 DFS 把它整片数出来。
- 11走到陆地 (0,3)：数过它，当前这座岛面积 = 1（还没超过最大 3）。
- 12走到陆地 (0,4)：数过它，当前这座岛面积 = 2（还没超过最大 3）。
- 13从 (0,4) 往下看 (1,4) 是水（0），不是陆地，这个方向不数。
- 14走到陆地 (1,3)：数过它，当前这座岛面积 = 3（还没超过最大 3）。
- 15从 (1,3) 往右看 (1,4) 是水（0），不是陆地，这个方向不数。
- 16走到陆地 (2,3)：数过它，当前这座岛面积 = 4，刷新了见过的最大面积 → 4。
- 17走到陆地 (2,2)：数过它，当前这座岛面积 = 5，刷新了见过的最大面积 → 5。
- 18走到陆地 (3,2)：数过它，当前这座岛面积 = 6，刷新了见过的最大面积 → 6。
- 19走到陆地 (3,1)：数过它，当前这座岛面积 = 7，刷新了见过的最大面积 → 7。
- 20走到陆地 (3,0)：数过它，当前这座岛面积 = 8，刷新了见过的最大面积 → 8。
- 21第 2 座岛数完，面积 = 8。它是目前见过最大的，最大面积保持 8。归档（变绿），继续往后扫。
- 22扫到 (3,4) 是没数过的陆地 → 发现第 3 座岛，从这里开始 DFS 把它整片数出来。
- 23走到陆地 (3,4)：数过它，当前这座岛面积 = 1（还没超过最大 8）。
- 24第 3 座岛数完，面积 = 1。没超过当前最大 8，最大面积不变。归档（变绿），继续往后扫。
- 25全部格子扫完，一共 3 座岛，最大的那座面积 = 8，返回 8。
⚠️ 容易写错的地方
✗ 错：数过的格不标记
✓ 对：走过一格立刻标记（改 0 或用 visited）
不标记会在相邻格之间来回数，面积无限膨胀甚至死循环
✗ 错：忘了更新全局最大
✓ 对：每座岛数完都和 best 比一次
只数不比，最后拿不到最大那座
✗ 错：只数第一座岛
✓ 对：外层双重循环要扫遍所有格子
岛可能有多座，漏扫就漏掉更大的岛
完整代码（Python / C++ / Java）
Python
def maxAreaOfIsland(grid):
R, C = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= R or j < 0 or j >= C: return 0
if grid[i][j] != 1: return 0 # 水/已数过
grid[i][j] = 0 # 标记已数过
area = 1
for di, dj in ((-1,0),(0,1),(1,0),(0,-1)):
area += dfs(i + di, j + dj)
return area
best = 0
for i in range(R):
for j in range(C):
if grid[i][j] == 1:
best = max(best, dfs(i, j))
return bestC++
class Solution {
int R, C;
int dfs(vector<vector<int>>& g, int i, int j) {
if (i < 0 || i >= R || j < 0 || j >= C) return 0;
if (g[i][j] != 1) return 0; // 水/已数过
g[i][j] = 0; // 标记已数过
int area = 1;
int d[5] = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; k++)
area += dfs(g, i + d[k], j + d[k + 1]);
return area;
}
public:
int maxAreaOfIsland(vector<vector<int>>& g) {
R = g.size(); C = g[0].size();
int best = 0;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (g[i][j] == 1)
best = max(best, dfs(g, i, j));
return best;
}
};Java
class Solution {
int R, C;
int[] d = {-1, 0, 1, 0, -1};
int dfs(int[][] g, int i, int j) {
if (i < 0 || i >= R || j < 0 || j >= C) return 0;
if (g[i][j] != 1) return 0; // 水/已数过
g[i][j] = 0; // 标记已数过
int area = 1;
for (int k = 0; k < 4; k++)
area += dfs(g, i + d[k], j + d[k + 1]);
return area;
}
public int maxAreaOfIsland(int[][] g) {
R = g.length; C = g[0].length;
int best = 0;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (g[i][j] == 1)
best = Math.max(best, dfs(g, i, j));
return best;
}
}复杂度
时间
O(R·C)
每个格子最多被访问一次（数过即标记）
空间
O(R·C)
最坏情况整张图是一座岛，递归栈深度到格子总数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 岛屿的最大面积 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么可以直接把陆地改成 0 当 visited，不另开一个 visited 矩阵？+
数过的陆地后面不再需要，改成 0（水）就等价于「已访问」标记，省一个矩阵的空间。若不允许改原数组，再单开 visited 即可。
DFS 和 BFS 都能做吗？+
都能。本质都是遍历连通块、累加格子数。DFS 用递归/栈写得短，BFS 用队列、能避免深图爆栈，二者复杂度相同。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 岛屿的最大面积 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。