LeetCode 695. 岛屿的最大面积

字数 1474 2025-10-25 22:15:07

LeetCode 695. 岛屿的最大面积

题目描述
给定一个由数字0和1组成的二维网格，其中1代表陆地，0代表水域。网格中的水平和垂直方向相连的1被视为同一块陆地。题目要求你找出这个网格中最大的陆地面积。一块陆地的面积被定义为组成这块陆地的1的个数。

解题过程

问题理解与核心思路
这道题和我们做过的“岛屿数量”问题非常相似，但目标不同。在“岛屿数量”中，我们只关心有多少块独立的陆地。而在这里，我们需要在找出所有独立陆地的同时，计算出每一块陆地的面积（即包含的1的个数），然后从中找出最大值。
核心思路依然是使用深度优先搜索（DFS） 或广度优先搜索（BFS）来遍历网格。当我们遇到一个未被访问过的‘1’（陆地）时，就以此点为起点，搜索整个相连的陆地区域，并在搜索过程中计数。
算法选择：深度优先搜索（DFS）
我们将使用DFS来解决这个问题。DFS的思路是“一条路走到黑”，对于当前访问的陆地，我们会递归地去访问它的上、下、左、右四个方向的相邻格子，直到当前陆地所在连通分量的所有陆地都被访问到。
详细步骤
- 步骤一：初始化
  我们需要一个与输入网格同样大小的二维数组（或者使用其他标记方法）来记录哪些格子已经被访问过，避免重复计算。不过，有一个更节省空间的方法：当我们访问过一个‘1’之后，我们将其值从1修改为0（即“淹没”这块陆地），这样它就不会被再次访问。这同时起到了标记访问和修改原网格的作用。
- 步骤二：遍历网格
  我们使用两层循环来遍历网格中的每一个格子。
  - 对于当前格子 grid[i][j]：
  - 如果它的值是0（水域），我们直接跳过。
  - 如果它的值是1（陆地），那么我们发现了一块新陆地的起点。我们从这个起点开始进行DFS，目的是计算出这块陆地的总面积。
- 步骤三：设计DFS函数
  我们需要设计一个递归函数，比如叫 dfs(i, j)，它的作用是计算并返回以 (i, j) 为起点的那块陆地的面积。
  - 递归终止条件（基本情况）：
    1. 当前坐标 (i, j) 超出了网格的边界。
    2. 当前格子的值是0（水域）。
      只要满足以上任意一个条件，说明这部分不是有效陆地，对面积没有贡献，返回0。
  - 递归过程（递归情况）：
    1. 如果当前格子是有效的、未被访问的陆地（值为1），我们首先将其标记为已访问（即将其值从1设置为0），这防止了后续的递归无限循环。
    2. 当前这块陆地本身面积为1。
    3. 然后，我们向四个方向（上、下、左、右）进行探索。当前陆地的总面积等于“自身的1”加上“四个方向邻居陆地面积的总和”。
    4. 将这四个方向返回的面积加起来，再加上自身的1，就是整个连通区域的面积。
  用伪代码表示这个函数：
```
函数 dfs(i, j):
  如果 i 或 j 越界，或者 grid[i][j] == 0, 返回 0
  否则：
    将 grid[i][j] 设置为 0  // 标记为已访问
    面积 area = 1  // 当前节点自身的面积
    area += dfs(i-1, j) // 上方
    area += dfs(i+1, j) // 下方
    area += dfs(i, j-1) // 左方
    area += dfs(i, j+1) // 右方
    返回 area
```
- 步骤四：比较并记录最大面积
  在主函数中，每当我们在步骤二的循环中遇到一个‘1’并调用DFS后，我们都会得到一个当前陆地的面积。我们将这个面积与之前记录的最大面积进行比较，更新最大值。
- 步骤五：返回结果
  当遍历完整个网格后，我们记录的最大面积就是整个网格中最大岛屿的面积，将其返回。
复杂度分析
- 时间复杂度：O(M × N)，其中M和N分别是网格的行数和列数。在最坏情况下，我们需要访问网格中的每一个格子一次。
- 空间复杂度：O(M × N)。主要取决于递归调用栈的深度。在最坏情况下，整个网格都是陆地，DFS的深度可能达到M×N。

总结
解决这个问题的步骤可以概括为：遍历网格 -> 发现陆地 -> DFS计算该陆地面积 -> 更新最大面积 -> 返回结果。关键在于DFS函数的设计，它通过递归的方式巧妙地计算出了连通区域的面积。

LeetCode 695. 岛屿的最大面积题目描述给定一个由数字0和1组成的二维网格，其中1代表陆地，0代表水域。网格中的水平和垂直方向相连的1被视为同一块陆地。题目要求你找出这个网格中最大的陆地面积。一块陆地的面积被定义为组成这块陆地的1的个数。解题过程问题理解与核心思路这道题和我们做过的“岛屿数量”问题非常相似，但目标不同。在“岛屿数量”中，我们只关心有多少块独立的陆地。而在这里，我们需要在找出所有独立陆地的同时，计算出每一块陆地的面积（即包含的1的个数），然后从中找出最大值。核心思路依然是使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历网格。当我们遇到一个未被访问过的‘1’（陆地）时，就以此点为起点，搜索整个相连的陆地区域，并在搜索过程中计数。算法选择：深度优先搜索（DFS）我们将使用DFS来解决这个问题。DFS的思路是“一条路走到黑”，对于当前访问的陆地，我们会递归地去访问它的上、下、左、右四个方向的相邻格子，直到当前陆地所在连通分量的所有陆地都被访问到。详细步骤步骤一：初始化我们需要一个与输入网格同样大小的二维数组（或者使用其他标记方法）来记录哪些格子已经被访问过，避免重复计算。不过，有一个更节省空间的方法：当我们访问过一个‘1’之后，我们将其值从1修改为0（即“淹没”这块陆地），这样它就不会被再次访问。这同时起到了标记访问和修改原网格的作用。步骤二：遍历网格我们使用两层循环来遍历网格中的每一个格子。对于当前格子 grid[i][j] ：如果它的值是0（水域），我们直接跳过。如果它的值是1（陆地），那么我们发现了一块新陆地的起点。我们从这个起点开始进行DFS，目的是计算出这块陆地的总面积。步骤三：设计DFS函数我们需要设计一个递归函数，比如叫 dfs(i, j) ，它的作用是计算并返回以 (i, j) 为起点的那块陆地的面积。递归终止条件（基本情况）：当前坐标 (i, j) 超出了网格的边界。当前格子的值是0（水域）。只要满足以上任意一个条件，说明这部分不是有效陆地，对面积没有贡献，返回0。递归过程（递归情况）：如果当前格子是有效的、未被访问的陆地（值为1），我们首先将其标记为已访问（即将其值从1设置为0），这防止了后续的递归无限循环。当前这块陆地本身面积为1。然后，我们向四个方向（上、下、左、右）进行探索。当前陆地的总面积等于“自身的1”加上“四个方向邻居陆地面积的总和”。将这四个方向返回的面积加起来，再加上自身的1，就是整个连通区域的面积。用伪代码表示这个函数：步骤四：比较并记录最大面积在主函数中，每当我们在步骤二的循环中遇到一个‘1’并调用DFS后，我们都会得到一个当前陆地的面积。我们将这个面积与之前记录的最大面积进行比较，更新最大值。步骤五：返回结果当遍历完整个网格后，我们记录的最大面积就是整个网格中最大岛屿的面积，将其返回。复杂度分析时间复杂度：O(M × N) ，其中M和N分别是网格的行数和列数。在最坏情况下，我们需要访问网格中的每一个格子一次。空间复杂度：O(M × N) 。主要取决于递归调用栈的深度。在最坏情况下，整个网格都是陆地，DFS的深度可能达到M×N。总结解决这个问题的步骤可以概括为：遍历网格 -> 发现陆地 -> DFS计算该陆地面积 -> 更新最大面积 -> 返回结果。关键在于DFS函数的设计，它通过递归的方式巧妙地计算出了连通区域的面积。