岛屿的最大面积

难度:

标签:

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 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
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

代码结果

运行时间: 35 ms, 内存: 16.6 MB

/*
 * 思路：
 * 1. 遍历矩阵，遇到1时使用DFS计算面积，标记访问过的土地。
 * 2. 使用Java Stream进行矩阵处理，计算最大面积。
 */
import java.util.stream.IntStream;
 
public class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        return IntStream.range(0, grid.length)
                .flatMap(i -> IntStream.range(0, grid[i].length)
                        .map(j -> (grid[i][j] == 1) ? dfs(grid, i, j) : 0))
                .max().orElse(0);
    }
 
    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0; // 标记为已访问
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }
}

解释

方法:

该题解采用深度优先搜索(DFS)的方法来解决问题。对于网格中的每个为1的点，以该点为起始进行DFS遍历，将遍历过的点置为0，并累加遍历的岛屿面积。在遍历过程中，递归地向上、下、左、右四个方向扩展，直到遇到边界或者遇到0为止。每次遍历后更新最大岛屿面积。遍历完整个网格后，即可得到最大的岛屿面积。

时间复杂度:

O(m*n)

空间复杂度:

O(m*n)

代码细节讲解

🦆

在DFS函数中，为什么在进入前需要检查当前位置是否为1？

▷

在DFS函数中检查当前位置是否为1是必要的，因为这个检查确定了当前位置是否是岛屿的一部分（即是否为陆地）。如果当前位置为0，则表示是水域，不应继续进行DFS。此外，这个检查也防止了对已经访问过并标记为0的位置重复访问，从而避免了无限递归和错误的面积计算。

🦆

递归调用dfs时，如果不将访问过的1置为0，会有什么后果？

▷

如果在递归调用dfs时不将访问过的1置为0，将导致算法重复访问同一个岛屿的部分。这种重复访问会造成无限递归，因为算法会不停地在已经访问过的岛屿部分之间循环。此外，它也会导致错误地计算岛屿的面积，因为同一块陆地会被多次计算。

🦆

在DFS中，遇到边界条件时直接返回0，这种处理方式是否总是适用于所有情况？

▷

在DFS中，遇到边界条件时返回0是一种常见的处理方式，用于标示已经到达不可继续探索的区域（如网格边界或水域）。这种处理方式在本题中是适用的，因为它简化了代码并防止了访问数组外的索引。然而，这种处理方式不一定适用于所有情况，具体依赖于问题的要求和边界的定义。在其他类型的DFS问题中，可能需要采取不同的边界处理策略。

🦆

函数maxAreaOfIsland中为什么需要两层循环遍历整个网格？

▷

函数maxAreaOfIsland中需要两层循环遍历整个网格是为了确保每个为1的点都被考虑作为岛屿的起始点进行DFS遍历。这样可以确保找到所有独立的岛屿，并计算出每个岛屿的面积。只有全面遍历整个网格，才能正确地计算出最大的岛屿面积。

相关问题

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

输入：grid = [[1]]
输出：4

示例 3：

输入：grid = [[1,0]]
输出：4

提示：

row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] 为 0 或 1

不同岛屿的数量计数二进制子串