LeetCode695.岛屿的最大面积

原题链接：岛屿的最大面积

题目描述

• 给定一个包含了一些0和1的非空二维数组grid，一个岛屿是由四个方向（水平或垂直）的1（代表土地）构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
• 找到给定的二维数组中最大的岛屿面积。
• 如果没有岛屿，则返回面积为0。

示例 1

[[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

[[0,0,0,0,0,0,0,0]]

• 对于上面这个给定的矩阵，返回0。

其他注意事项

• 给定的矩阵grid的长度和宽度都不超过50。

思路描述

核心——DFS问题。

1. 首先需要一个DFS方法，如果该点为1，则向四个方向递归；如果该点为0，则方法直接返回。该方法需要判断边界情况。
2. 需要一个跟grid大小一样的boolean visited[][]数组来记录该点是否已访问，防止重复访问。
3. 外层双重循环遍历所有的点，并比较每个点的DFS方法返回值，得到最大值。

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        // 记录该节点是否访问过
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        // 记录最大值
        int max = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                max = Math.max(max, dfs(i, j, grid, visited));
            }
        }
        return max;
    }

    private int dfs(int i, int j, int[][] grid, boolean[][] visited) {
        // 边界判断
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
            return 0;
        }
        // 重复访问判断
        if (visited[i][j]) {
            return 0;
        }
        // 岛屿为0、1判断
        if (grid[i][j] == 0) {
            return 0;
        }
        // 标记该点为已访问
        visited[i][j] = true;
        // 四个方向递归
        return 1 + dfs(i-1, j, grid, visited)
                + dfs(i+1, j, grid, visited)
                + dfs(i, j-1, grid, visited)
                + dfs(i, j+1, grid, visited);
    }
}

优化思路

• 如果原grid数组可以被修改，那么可以不使用辅助空间visited[][]二维数组，直接修改原数组来做标记

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        // 记录最大值
        int max = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                int temp = DFS(i, j, grid);
                max = temp > max ? temp : max;
            }
        }
        return max;
    }

    public int DFS(int i, int j, int[][] grid) {
        // 边界判断
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
            return 0;
        }

        // 岛屿为0、1判断
        if (grid[i][j] == 0) {
            return 0;
        }

        // 标记grid[i][j] = 0
        grid[i][j] = 0;
        // 四个方向递归
        return 1 + DFS(i-1, j, grid)
                + DFS(i+1, j, grid)
                + DFS(i, j-1, grid)
                + DFS(i, j+1, grid);
    }
}

---

一年又一年，字节跳动 Lark（飞书） 研发团队又双叒叕开始招新生啦！

【内推码】：GTPUVBA

【内推链接】：https://job.toutiao.com/s/JRupWVj

【招生对象】：20年9月后~21年8月前 毕业的同学

【报名时间】：6.16-7.16（提前批简历投递只有一个月抓住机会哦！）

【画重点】：提前批和正式秋招不矛盾！面试成功，提前锁定Offer；若有失利，额外获得一次面试机会，正式秋招开启后还可再次投递。

---