LeetCode695、岛屿的最大面积

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。 岛屿的面积是岛上值为 1 的单元格的数目。 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1： JPaxbLaHmoyie1xQZ0Tc7WNQnxd.jpg

输入： 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

题目解析

题目在说什么

想象你有一张地图，地图被分成了很多小格子。每个格子要么是陆地（用数字1表示），要么是水（用数字0表示）。陆地格子如果上下左右相邻（斜对角不算），就组成一个“岛屿”。题目要你找出所有岛屿中，面积最大的那个有多大。面积就是岛屿里陆地格子的总数。

比如，一个岛屿如果有6个连在一起的1，它的面积就是6。如果地图上全是水，那最大面积就是0。

思路是怎么来的

我们可以把这个问题想象成“在一片海域里找最大的陆地群”。最直接的办法就是：把地图上的每个格子都检查一遍，遇到陆地就看看它属于哪个岛屿，数一数这个岛屿有多大，然后记下最大的那个数。

但是，怎么确保我们不会重复数同一个岛屿呢？一个简单的方法是：每当我们发现一块新的陆地，就从它开始，像“贪吃蛇”一样把整个岛屿的所有格子都走一遍，每走一个格子就标记一下“已访问”，这样下次就不会再数它了。

这种“从一个点出发，沿着上下左右一直走到不能再走”的方法，就是深度优先搜索（DFS）。你可以想象成：你站在一块陆地上，先往北走，走到不能走再回头，然后往东、南、西……直到把整个岛屿的每个角落都踏遍。

代码逐步拆解

我们来看参考代码，它用DFS实现了这个思路。

1. 准备工作

private int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int x, y;
private int area;

• DIRECTIONS：这是一个方向数组，表示上下左右四个方向。{0,1}是向右，{1,0}是向下，{0,-1}是向左，{-1,0}是向上。这样我们就能方便地计算相邻格子的坐标。
• x, y：用来存地图的行数和列数。
• area：临时变量，用来记录当前正在探索的岛屿的面积。

2. 主函数：遍历每个格子

public int maxAreaOfIsland(int[][] grid) {
    x = grid.length;      // 行数
    y = grid[0].length;   // 列数
    int ans = 0;          // 最终答案，最大面积
    boolean[][] checkList = new boolean[x][y];  // 标记格子是否访问过

• 我们创建一个和地图一样大的checkList，初始全是false，表示都没访问过。
• ans用来存目前找到的最大面积，初始为0。

3. 双重循环：找起点

for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        if (grid[i][j] == 1 && !checkList[i][j]) {
            area = 0;              // 每次新岛屿开始，面积清零
            DFS(grid, i, j, checkList);  // 从(i,j)开始探索整个岛屿
            ans = Math.max(ans, area);   // 更新最大面积
        }
    }
}

• 我们从上到下、从左到右，一个一个格子检查。
• 如果发现一个格子是陆地（grid[i][j]==1）并且还没被访问过（!checkList[i][j]），那说明我们找到了一个新岛屿的起点。
• 在开始探索前，先把area设为0，然后调用DFS函数去“走遍”这个岛屿。
• 探索结束后，area就是这个岛屿的面积，我们用它和ans比较，取较大的那个。

4. DFS函数：深入探索岛屿

private void DFS(int[][] grid, int i, int j, boolean[][] checkList) {
    checkList[i][j] = true;  // 标记当前格子已访问
    area++;                  // 面积加1

• 一进入DFS，首先把当前格子标记为已访问，然后面积加1。这就像你踏上这块陆地，先插个旗子说“我来过了”，然后数上1。

    for (int[] dir : DIRECTIONS) {
        int next_i = i + dir[0];
        int next_j = j + dir[1];
        if (next_i >= 0 && next_i < x && next_j >= 0 && next_j < y &&
                !checkList[next_i][next_j] && grid[next_i][next_j] == 1) {
            DFS(grid, next_i, next_j, checkList);
        }
    }
}

• 然后，我们尝试向上下左右四个方向各走一步，得到邻居的坐标(next_i, next_j)。
• 对于每个邻居，我们要检查三个条件：

1. 没有越界：坐标在0到x-1、0到y-1之间。