Go after
0%

岛屿的最大面积-LeetCode

发表于 更新于 分类于 ， 阅读次数：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

岛屿的最大面积

岛屿的最大面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
695岛屿的最大面积:
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 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

Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class MaxAreaOfIsland {
    public static void main(String[] args) {
        int[][] 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}};
        System.out.println(maxAreaOfIsland(grid));
    }

    // 每次调用的时候假设num为1，进入后判断不是岛屿，则直接返回0，就可以避免错误的情况。
    // 每次找到岛屿，把找到的岛屿改成0，这是传说中的沉岛思想，就是遇到岛屿就把沉默。
    public static int maxAreaOfIsland(int[][] grid){
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    res = Math.max(res,dfs(i, j, grid));//math.max选取岛屿中的最大值，不控制时，获得的岛屿值为最后岛屿值
                }
            }
        }
        return res;
    }
    //深度算法，递归实现
    private static int dfs(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;//沉岛思想
        int num = 1;//没进入if判断，则是岛屿
        num += dfs(i + 1, j, grid);
        num += dfs(i, j + 1, grid);
        num += dfs(i - 1, j, grid);
        num += dfs(i, j - 1, grid);
        return num;
    }
}