695. 岛屿的最大面积(中等)

Posted on In Views:

1，问题描述

695. 岛屿的最大面积

难度：中等

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

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

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

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

img

1
2
3
输入：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：

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

2，初步思考

​ 遍历、染色、清点比较大小

​ 我第一次使用了hashSet进行处理，之后看完官方答案后使用的是染色法处理

3，代码处理

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class _695岛屿的最大面积 {

    // 官方的解法更快
    public int maxAreaOfIsland_gov(int[][] grid) {
        rows = grid.length;
        columns = grid[0].length;// 前行后列
        maxArea = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                maxArea = Math.max(dfs_gov(grid, i, j, 0), maxArea);
            }
        }
        return maxArea;
    }

    private int dfs_gov(int[][] grid, int i, int j, int areaCur) {
        if (i < 0 || i >= rows || j < 0 || j >= columns || grid[i][j] != 1) {
            return areaCur;
        }
        areaCur++;
        grid[i][j] = 2;

        areaCur += dfs_gov(grid, i - 1, j, 0);
        areaCur += dfs_gov(grid, i + 1, j, 0);
        areaCur += dfs_gov(grid, i, j - 1, 0);
        areaCur += dfs_gov(grid, i, j + 1, 0);
        return areaCur;
    }

    public int maxAreaOfIsland(int[][] grid) {
        Set<String> set = new HashSet<>();
        rows = grid.length;
        columns = grid[0].length;// 前行后列
        columnsIndex = grid[0].length + 1;// 前行后列
        maxArea = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == 1) {
                    set.add(i + "," + j);
                }
            }
        }
        while (!set.isEmpty()) {
            int sizeCur = set.size();
            int maxAreaCur = 1;
            String key = new ArrayList<>(set).getFirst();
            dfs(set, key, maxAreaCur);
            maxArea = Math.max(maxArea, sizeCur - set.size());
        }
        return maxArea;
    }

    int rows = 0, columns = 0, columnsIndex = 0, maxArea = 0;

    private void dfs(Set<String> set, String key, int maxAreaCur) {
        set.remove(key);
        String[] split = key.split(",");
        int i = Integer.parseInt(split[0]), j = Integer.parseInt(split[1]);
        String key1 = (i - 1) + "," + j;// 上
        String key2 = (i + 1) + "," + j;// 下
        String key3 = i + "," + (j - 1);// 左
        String key4 = i + "," + (j + 1);// 右
        if (set.contains(key1)) {
            dfs(set, key1, maxAreaCur + 1);
        }
        if (set.contains(key2)) {
            dfs(set, key2, maxAreaCur + 1);
        }
        if (set.contains(key3)) {
            dfs(set, key3, maxAreaCur + 1);
        }
        if (set.contains(key4)) {
            dfs(set, key4, maxAreaCur + 1);
        }
    }

    public static void main(String[] args) {
        _695岛屿的最大面积 island = new _695岛屿的最大面积();
//        System.out.println(island.maxAreaOfIsland(new int[][]{
//                {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(island.maxAreaOfIsland_gov(new int[][]{{1, 1, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {1, 1, 0, 1, 1}}));
    }
}