695. 岛屿的最大面积
题目描述
输入一个 m x n 的网格 grid，每个格子为 0（水）或 1（陆地）。网格外侧都视为水。
在上、下、左、右四个方向相邻的陆地格子连在一起，组成一座岛屿；斜对角不算相邻。一座岛屿的面积是它包含的陆地格子数。
返回面积最大的岛屿的面积。如果没有任何陆地，返回 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
解释：最大的岛有 6 个格子；斜向接触的格子不算同一座岛，所以不是 11。
示例 2
输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0
解释：网格中没有陆地。
数据范围
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]为 0 或 1。
解题思路
逐格扫描。遇到 1 就从它出发做 DFS（用显式栈），把整座岛屿的格子一个个弹出并计数，同时把访问过的陆地改成 0，避免重复计算。一座岛搜索结束得到面积 area，用它更新最大值 best。
为什么正确
栈中的格子都已被改成 0 且尚未计数；每次弹出一个格子 area 恰好加 1，因此 DFS 结束时 area 就是整座岛的面积。
复杂度分析
时间 O(mn)，每格最多入栈一次；空间 O(mn)（栈最坏情况）。
易错点
入栈时就要把格子改成 0；如果等到弹出时才改，同一个格子可能被多个邻居重复入栈，面积会被算多。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
grid[r][c] = 0
stack = [(r, c)]
area = 0
while stack:
x, y = stack.pop()
area += 1
for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = 0
stack.append((nx, ny))
best = max(best, area)
return bestclass Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
int best = 0;
int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
grid[r][c] = 0;
Deque<int[]> st = new ArrayDeque<>();
st.push(new int[]{r, c});
int area = 0;
while (!st.isEmpty()) {
int[] cur = st.pop();
area++;
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d], ny = cur[1] + dy[d];
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == 1) {
grid[nx][ny] = 0;
st.push(new int[]{nx, ny});
}
}
}
best = Math.max(best, area);
}
}
}
return best;
}
}class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int best = 0;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
grid[r][c] = 0;
vector<pair<int, int>> st = {{r, c}};
int area = 0;
while (!st.empty()) {
auto [x, y] = st.back();
st.pop_back();
area++;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == 1) {
grid[nx][ny] = 0;
st.push_back({nx, ny});
}
}
}
best = max(best, area);
}
}
}
return best;
}
};func maxAreaOfIsland(grid [][]int) int {
m, n := len(grid), len(grid[0])
best := 0
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] == 1 {
grid[r][c] = 0
st := [][2]int{{r, c}}
area := 0
for len(st) > 0 {
x, y := st[len(st)-1][0], st[len(st)-1][1]
st = st[:len(st)-1]
area++
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if 0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == 1 {
grid[nx][ny] = 0
st = append(st, [2]int{nx, ny})
}
}
}
if area > best {
best = area
}
}
}
}
return best
}var maxAreaOfIsland = function(grid) {
const m = grid.length, n = grid[0].length;
let best = 0;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
grid[r][c] = 0;
const st = [[r, c]];
let area = 0;
while (st.length > 0) {
const [x, y] = st.pop();
area++;
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] === 1) {
grid[nx][ny] = 0;
st.push([nx, ny]);
}
}
}
best = Math.max(best, area);
}
}
}
return best;
};function maxAreaOfIsland(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
let best = 0;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1) {
grid[r][c] = 0;
const st = [[r, c]];
let area = 0;
while (st.length > 0) {
const [x, y] = st.pop();
area++;
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] === 1) {
grid[nx][ny] = 0;
st.push([nx, ny]);
}
}
}
best = Math.max(best, area);
}
}
}
return best;
}