题目

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

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

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

示例 1:

• 输入: grid = [[1, 0], [0, 1]]

• 输出: 3

• 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。 示例 2:

• 输入: grid = [[1, 1], [1, 0]]

• 输出: 4

• 解释: 将一格0变成1，岛屿的面积扩大为 4。 示例 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.第一步，先深度优先遍历出陆地，获取到所有的陆地面积，并且将同一块陆地中的格子值置换为同一索引值，该索引为记录该陆地面积的索引下标值
• 2.第二部，遍历海洋，找到相邻陆地面积最大的海洋格子

细化思路：

• 1.先计算出所有岛屿的面积，并全部记录下来，便于后面给填海时判断总面积大小使用。
• 2.按照通用的DFS遍历办法，需要防止遍历过的节点重复遍历，所以需要将遍历过的节点进行赋值变更，便于下次去重，避免重复遍历。0（海洋）,1（陆地），所以这里建议为了避免和原值冲突，index值从2开始，一旦有陆地就依次遍历累加，这样index将代表岛屿面积map中的索引值，便于后续查找面积。
• 3.遍历海洋，一旦发现海洋，就判断上下左右格子是否为陆地，此处要特别注意的是，有可能四周皆为陆地，但需要判断这些陆地是同一块陆地，还是不同的陆地，避免陆地面积重复累加，这里是个易错点。

解法

class Solution {
    /**
     * 1.第一步，先深度优先遍历出陆地，获取到所有的陆地面积，并且将同一块陆地中的格子值置换为同一索引值，该索引为记录该陆地面积的索引下标值
     * 2.第二部，遍历海洋，找到相邻陆地面积最大的海洋格子
     */
    public static int largestIsland(int[][] grid) {
        //用来记录每次遍历中每个陆地的面积大小
        int res = 0;
        int maxArea =0;
        //索引值从2开始，避免和0（海洋）,1（陆地）值冲突
        int index = 2;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //1.深度优先，先遍历出陆地面积
        for (int x = 0; x< grid.length; x++){
            for (int y=0; y<grid[0].length; y++){
                if( grid[x][y] == 1 ){
                    int a = area(grid, x, y, index);
                    maxArea = Math.max(a, res);
                    map.put(index, a);
                    ++index;
                }
            }
        }
        //2.遍历海洋，找到相邻陆地面积最大的海洋格子
        int plusRes = 0;
        for (int x = 0; x< grid.length; x++){
            for (int y=0; y<grid[0].length; y++){
                //如果是0（海洋）
                if( grid[x][y] == 0 ){
                    int plusArea = plusArea(grid, x, y, map);
                    plusRes = Math.max(plusArea, plusRes);
                }
            }
        }
        //可能都没有海洋，全是陆地，则再次判断，直接返回陆地最大值
        plusRes = Math.max(maxArea, plusRes);
        return plusRes;
    }

    private static int plusArea(int[][] grid, int x, int y, Map<Integer, Integer> map){
        if( !isArea(grid, x, y) ){
            return 0;
        }
        if( grid[x][y] != 0 ){
            return 0;
        }
        Integer size = 0;
        //叠加面积很关键的一步，记得去重，因为海洋四周接壤的土地有可能是同一块陆地
        Set<Integer> set = new HashSet<Integer>();
        if( isArea(grid, x-1, y) && grid[x-1][y] >= 2 ){
            set.add(grid[x-1][y]);
        }
        if( isArea(grid, x+1, y) && grid[x+1][y] >=2 ){
            set.add(grid[x+1][y]);
        }
        if( isArea(grid, x, y-1) && grid[x][y-1] >=2 ){
            set.add(grid[x][y-1]);
        }
        if( isArea(grid, x, y+1) && grid[x][y+1] >=2 ){
            set.add(grid[x][y+1]);
        }
        for (Integer num : set){
            size += map.get(num);
        }
        //海洋变土地，+1
        ++size;
        return size;
    }

    private static int area(int[][] grid, int x, int y, int index){
        if( !isArea(grid, x, y) ){
            return 0;
        }
        if( grid[x][y] != 1 ){
            return 0;
        }
        //用index来代表同一块陆地存放面积的索引值
        grid[x][y] = index;
        return 1
                + area(grid , x+1, y,index)
                + area(grid , x-1, y,index)
                + area(grid , x, y+1,index)
                + area(grid , x, y-1,index);
    }

    private static boolean isArea(int[][] grid, int x, int y){
        return 0<=x && x<grid.length && 0<=y && y < grid[0].length;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现