LeetCode 「中等」695.岛屿的最大面积
题目描述
岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例
输入：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
输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
解答
DFS（深度优先搜索）
关键思路
- 遍历网格
- 遍历整个网格，找到值为
1的单元格，这表示一个岛屿的起点
- DFS 递归
- 对于每个起点，使用 DFS 递归地计算该岛屿的面积
- 在递归过程中，将访问过的陆地单元格标记为
0，以避免重复计算
- 更新最大面积
- 每次计算完一个岛屿的面积后，更新全局的最大面积
- 返回结果
- 遍历结束后，返回最大面积
具体步骤
- 初始化变量
maxArea：用于存储最大岛屿的面积row和col：网格的行数和列数
- 定义 DFS 函数
- 递归地计算一个岛屿的面积
- 检查边界条件和单元格的值，确保只计算陆地单元格
- 遍历网格
- 对于每个单元格，如果值为
1，则调用 DFS 函数计算该岛屿的面积，并更新最大面积
- 返回结果
- 返回计算得到的最大面积
Code
/**
* @param {number[][]} grid
* @return {number}
*/
var maxAreaOfIsland = function(grid) {
const row = grid.length;
const col = grid[0].length;
let maxArea = 0;
const dfs = (r, c) => {
// 检查边界条件和单元格值
if (r < 0 || r >= row || c < 0 || c >= col || grid[r][c] !== 1) return 0;
// 标记当前单元格为已访问
grid[r][c] = 0;
// 递归计算当前岛屿的面积
let area = 1;
area += dfs(r - 1, c);
area += dfs(r + 1, c);
area += dfs(r, c - 1);
area += dfs(r, c + 1);
return area;
};
for (let i = 0; i < row; ++i) {
for (let j = 0; j < col; ++j) {
if (grid[i][j] === 1) {
// 计算当前岛屿的面积
const islandArea = dfs(i, j);
// 更新最大面积
maxArea = Math.max(islandArea, maxArea);
}
}
}
return maxArea;
};