Hard
题目描述
给你一个大小为 n x n 二进制矩阵 grid。你最多只能将一个 0 变成 1。
返回执行此操作后，grid 中最大的岛屿面积。
岛屿由一组上、下、左、右四个方向相连的 1 形成。
示例 1：
输入: grid = [[1,0],[0,1]]
输出: 3
解释: 将一个0变成1，连接两个1，然后我们得到了一个面积为3的岛屿。
示例 2：
输入: grid = [[1,1],[1,0]]
输出: 4
解释: 将0变成1，使得岛屿更大，面积为4。
示例 3：
输入: grid = [[1,1],[1,1]]
输出: 4
解释: 没有0可以让我们变成1，只有一个面积为4的岛屿。
提示：
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j]的值为0或1
解题思路
这道题的核心思路是先计算所有已存在岛屿的面积，然后尝试将每个 0 变成 1，看能连接哪些岛屿。
解法一：暴力枚举（简单但效率低）
对每个 0 位置，临时设为 1，然后用 DFS 计算新形成的岛屿面积。时间复杂度 O(n⁴)。
解法二：岛屿预处理 + 并查集/DFS（推荐）
- 第一步： 给每个岛屿分配唯一 ID，并记录每个岛屿的面积
- 第二步： 遍历所有
0位置，检查其四个方向相邻的不同岛屿，计算连接后的总面积
具体实现：
- 使用 DFS 遍历所有
1，给每个连通的岛屿分配从 2 开始的 ID（避免与原始值冲突） - 用哈希表记录每个岛屿 ID 对应的面积
- 遍历每个
0，检查四个方向的相邻岛屿 ID，累加面积 - 注意要去重，避免同一个岛屿被重复计算
时间复杂度：O(n²)，空间复杂度：O(n²)
代码实现
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
unordered_map<int, int> islandSize; // 岛屿ID -> 面积
int islandId = 2; // 从2开始分配ID
int maxArea = 0;
// 第一步：给每个岛屿分配ID并计算面积
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = dfs(grid, i, j, islandId);
islandSize[islandId] = area;
maxArea = max(maxArea, area);
islandId++;
}
}
}
// 第二步：尝试每个0位置
vector<int> directions = {-1, 0, 1, 0, -1};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
unordered_set<int> neighborIds;
for (int d = 0; d < 4; d++) {
int ni = i + directions[d];
int nj = j + directions[d + 1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] > 1) {
neighborIds.insert(grid[ni][nj]);
}
}
int totalArea = 1; // 当前0变成1
for (int id : neighborIds) {
totalArea += islandSize[id];
}
maxArea = max(maxArea, totalArea);
}
}
}
return maxArea;
}
private:
int dfs(vector<vector<int>>& grid, int i, int j, int id) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1) {
return 0;
}
grid[i][j] = id;
return 1 + dfs(grid, i - 1, j, id) + dfs(grid, i + 1, j, id) +
dfs(grid, i, j - 1, id) + dfs(grid, i, j + 1, id);
}
};
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
island_size = {} # 岛屿ID -> 面积
island_id = 2 # 从2开始分配ID
max_area = 0
def dfs(i, j, id):
if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
return 0
grid[i][j] = id
return 1 + dfs(i - 1, j, id) + dfs(i + 1, j, id) + \
dfs(i, j - 1, id) + dfs(i, j + 1, id)
# 第一步：给每个岛屿分配ID并计算面积
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
area = dfs(i, j, island_id)
island_size[island_id] = area
max_area = max(max_area, area)
island_id += 1
# 第二步：尝试每个0位置
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
neighbor_ids = set()
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
neighbor_ids.add(grid[ni][nj])
total_area = 1 # 当前0变成1
for id in neighbor_ids:
total_area += island_size[id]
max_area = max(max_area, total_area)
return max_area
public class Solution {
public int LargestIsland(int[][] grid) {
int n = grid.Length;
Dictionary<int, int> islandSize = new Dictionary<int, int>();
int islandId = 2;
int maxArea = 0;
// 第一步：给每个岛屿分配ID并计算面积
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
int area = DFS(grid, i, j, islandId);
islandSize[islandId] = area;
maxArea = Math.Max(maxArea, area);
islandId++;
}
}
}
// 第二步：尝试每个0位置
int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
HashSet<int> neighborIds = new HashSet<int>();
for (int d = 0; d < 4; d++) {
int ni = i + directions[d, 0];
int nj = j + directions[d, 1];
if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] > 1) {
neighborIds.Add(grid[ni][nj]);
}
}
int totalArea = 1;
foreach (int id in neighborIds) {
totalArea += islandSize[id];
}
maxArea = Math.Max(maxArea, totalArea);
}
}
}
return maxArea;
}
private int DFS(int[][] grid, int i, int j, int id) {
if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || grid[i][j] != 1) {
return 0;
}
grid[i][j] = id;
return 1 + DFS(grid, i - 1, j, id) + DFS(grid, i + 1, j, id) +
DFS(grid, i, j - 1, id) + DFS(grid, i, j + 1, id);
}
}
var largestIsland = function(grid) {
const n = grid.length;
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const islandSizes = new Map();
let islandId = 2;
let maxSize = 0;
function dfs(i, j, id) {
if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] !== 1) {
return 0;
}
grid[i][j] = id;
let size = 1;
for (let [di, dj] of directions) {
size += dfs(i + di, j + dj, id);
}
return size;
}
// Label islands and record their sizes
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
let size = dfs(i, j, islandId);
islandSizes.set(islandId, size);
maxSize = Math.max(maxSize, size);
islandId++;
}
}
}
// Try changing each 0 to 1
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
let neighborIds = new Set();
let newSize = 1;
for (let [di, dj] of directions) {
let ni = i + di, nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] > 1) {
neighborIds.add(grid[ni][nj]);
}
}
for (let id of neighborIds) {
newSize += islandSizes.get(id);
}
maxSize = Math.max(maxSize, newSize);
}
}
}
return maxSize;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(n²) |