LeetCode 827. 最大人工岛

Categories:

题目描述
思路分析
1. 解法一：染色 + 枚举翻转（推荐）
相似题目

题目描述

✅ 827. 最大人工岛

思路分析

解法一：染色 + 枚举翻转（推荐）

核心思路：

先 DFS/BFS 给每个岛屿染色编号并统计面积。

对每个 0 格子，查看四邻的岛屿编号，累加不同岛屿的面积再加 1。

取最大值，若原本全为 1，则返回 n*n。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示边长。

空间复杂度：O(n^2)，用于标记与递归栈。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    private int n;
    private int[][] grid;
    private int id = 2;

    public int largestIsland(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        Map<Integer, Integer> area = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int a = dfs(i, j, id);
                    area.put(id, a);
                    id++;
                }
            }
        }

        int best = 0;
        for (int val : area.values()) {
            best = Math.max(best, val);
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    continue;
                }

                Set<Integer> seen = new HashSet<>();
                int sum = 1;
                for (int k = 0; k < 4; k++) {
                    int ni = i + dr[k];
                    int nj = j + dc[k];
                    if (ni < 0 || ni >= n || nj < 0 || nj >= n) {
                        continue;
                    }

                    int idx = grid[ni][nj];
                    if (idx > 1 && seen.add(idx)) {
                        sum += area.get(idx);
                    }
                }

                best = Math.max(best, sum);
            }
        }

        return best == 0 ? n * n : best;
    }

    private int dfs(int r, int c, int idx) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) {
            return 0;
        }

        grid[r][c] = idx;
        int res = 1;
        res += dfs(r - 1, c, idx);
        res += dfs(r + 1, c, idx);
        res += dfs(r, c - 1, idx);
        res += dfs(r, c + 1, idx);
        return res;
    }
}

func largestIsland(grid [][]int) int {
	n := len(grid)
	id := 2
	area := make(map[int]int)

	var dfs func(r int, c int, idx int) int
	dfs = func(r int, c int, idx int) int {
		if r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1 {
			return 0
		}
		grid[r][c] = idx
		res := 1
		res += dfs(r-1, c, idx)
		res += dfs(r+1, c, idx)
		res += dfs(r, c-1, idx)
		res += dfs(r, c+1, idx)
		return res
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				a := dfs(i, j, id)
				area[id] = a
				id++
			}
		}
	}

	best := 0
	for _, v := range area {
		if v > best {
			best = v
		}
	}

	dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] != 0 {
				continue
			}

			seen := make(map[int]bool)
			sum := 1
			for _, d := range dirs {
				ni := i + d[0]
				nj := j + d[1]
				if ni < 0 || ni >= n || nj < 0 || nj >= n {
					continue
				}
				idx := grid[ni][nj]
				if idx > 1 && !seen[idx] {
					seen[idx] = true
					sum += area[idx]
				}
			}

			if sum > best {
				best = sum
			}
		}
	}

	if best == 0 {
		return n * n
	}
	return best
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS/BFS
694. 不同岛屿的数量	中等	DFS
1020. 飞地的数量	中等	DFS/BFS
1254. 统计封闭岛屿的数目	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/39754511