图解LeetCode——827. 最大人工岛（难度：困难）

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

二、示例

2.1> 示例 1:

【输入】 grid = [[1, 0], [0, 1]]
【输出】 3
【解释】 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

2.2> 示例 2:

【输入】 grid = [[1, 1], [1, 0]]
【输出】 4
【解释】 将一格0变成1，岛屿的面积扩大为 4。

2.3> 示例 3:

【输入】 grid = [[1, 1], [1, 1]]
【输出】 4
【解释】 没有0可以让我们变成1，面积依然为 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 为 0 或 1

三、解题思路

根据题意，我们可以知道整个“矩阵地图”中，是由岛屿（格子值为：1）和海洋（格子值为：0）组成的。那么，题目要求计算“经过某些操作”之后的岛屿面积，而岛屿是不同的，所以我们可以在遍历整个矩阵的过程中，对不同的岛屿进行编号。由于0和1已经被使用了，那么岛屿的编号我们就从2开始，当遍历到新的岛屿编号加1。如下图所示，我们遍历出来了编号为2~8的岛屿。并且，在遍历过程中，将每个岛屿的面积也统计出来，并保存到Map中（key=岛屿编号；value=岛屿面积）。如下图所示：

那么，下一步就需要根据题意的要求——即：“最多只能将一格0变为1”。那么我们遍历矩阵中的所有格子，只有当格子是海洋（格子值为：0）时，我们来判断其上、下、左、右格子的值，再来结合Map中存储的岛屿编号与面积的对应关系，进行岛屿面积计算即可。以下图为例，在我们遍历的这个格子周围：上格子值为：2，下格子值为：6，左格子为：0，右格子为：0，所以我们可以知道这块海洋格子与岛屿2和岛屿6是相邻的，那么总的面积就是：岛屿2面积（10）+ 岛屿6面积（4）+ 海洋格子翻转面积（1）= 15。通过这种方式，将遍历所有格子后，最大的岛屿面积作为方法返回值即可。

这里再补充说一下，对于每个格子遍历的时候，我们采用深度优先遍历方式，即：先后深度的去遍历该格子的上方向、下方向、左方向和右方向。

为了防止遍历不同格子时，出现重复遍历，我们采取遍历到“岛屿”后，将格子值赋值为岛屿编号的方式。那么，终止深度遍历的条件如下所示：

条件一：遍历格子下标已经越界，即：不满足 row >=0 && row < grid.length && column >= 0 && column < grid.length条件二：遍历的格子不为1。即：不遍历海洋格子和已遍历编号过的岛屿。

四、代码实现

class Solution {
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0) return 1;
        int result = 0, index = 2;
        HashMap<Integer, Integer> areasMap = new HashMap();
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++)
                if (grid[i][j] == 1) areasMap.put(index, calculateAreas(index++, grid, i, j)); // 只计算未编号的岛屿

        if (areasMap.size() == 0) return 1; // 没有岛屿，全是海洋
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> islands = getIslands(grid, i, j);
                    if (islands.size() == 0) continue; // 周围没有岛屿
                    result = Math.max(result, islands.stream().map(item -> areasMap.get(item)).reduce(Integer::sum).orElse(0) + 1);
                }
            }
        }
        if (result == 0) return areasMap.get(2); // 全是岛屿，没有海洋
        return result;
    }

    public int calculateAreas(int index, int[][] grid, int row, int column) {
        if (!isLegal(grid, row, column) || grid[row][column] != 1) return 0;
        grid[row][column] = index;
        return calculateAreas(index, grid, row + 1, column) + calculateAreas(index, grid, row - 1, column) + calculateAreas(index, grid, row, column - 1) + calculateAreas(index, grid, row, column + 1) + 1;
    }

    public boolean isLegal(int[][] grid, int row, int column) {
        return row >= 0 && row < grid.length && column >= 0 && column < grid[0].length;
    }

    public Set<Integer> getIslands(int[][] grid, int row, int column) {
        Set<Integer> result = new HashSet<>();
        if (isLegal(grid, row + 1, column) && grid[row + 1][column] != 0)
            result.add(grid[row + 1][column]);
        if (isLegal(grid, row - 1, column) && grid[row - 1][column] != 0)
            result.add(grid[row - 1][column]);
        if (isLegal(grid, row, column - 1) && grid[row][column - 1] != 0)
            result.add(grid[row][column - 1]);
        if (isLegal(grid, row, column + 1) && grid[row][column + 1] != 0)
            result.add(grid[row][column + 1]);
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」