题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，找出其中最大的岛屿面积。岛屿总是被水包围，并且每个岛屿只能由水平或垂直方向相邻的陆地连接。

解题思路

• 方法1：使用并查集来解决集合问题。
• 方法2：使用深度优先搜索（DFS）来探索岛屿面积。

Java代码示例

import java.util.*;

public class Solution {
    public int findMaxIslandArea(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        UnionFind uf = new UnionFind();
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    int index = i * cols + j;
                    uf.find(index);

                    for (int k = 0; k < 4; k++) {
                        int newX = i + dx[k];
                        int newY = j + dy[k];
                        int newIndex = newX * cols + newY;
                        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 1) {
                            uf.union(index, newIndex);
                        }
                    }
                }
            }
        }

        return uf.getMaxSize();
    }

    static class UnionFind {
        Map parent = new HashMap<>();
        Map sizeMap = new HashMap<>();
        int maxSize = 0;

        int find(int x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
                sizeMap.put(x, 1);
                maxSize = Math.max(maxSize, 1);
            }

            int hi = 0;
            while (x != parent.get(x)) {
                x = parent.get(x);
                hi++;
            }

            for (hi--; hi >= 0; hi--) {
                parent.put(hi, x);
            }

            return x;
        }

        void union(int a, int b) {
            int fa = find(a);
            int fb = find(b);
            if (fa != fb) {
                int sa = sizeMap.get(fa);
                int sb = sizeMap.get(fb);
                int big = sa >= sb ? fa : fb;
                int small = big == fa ? fb : fa;
                parent.put(small, big);
                sizeMap.put(big, sa + sb);
                maxSize = Math.max(maxSize, sa + sb);
            }
        }

        int getMaxSize() {
            return maxSize;
        }
    }
}

Go代码示例

package main

func findMaxIslandArea(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	uf := NewUnionFind()
	rows, cols := len(grid), len(grid[0])
	dx, dy := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] == 1 {
				index := i*cols + j
				uf.Find(index)

				for k := 0; k < 4; k++ {
					newX, newY := i+dx[k], j+dy[k]
					newIndex := newX*cols + newY
					if newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 1 {
						uf.Union(index, newIndex)
					}
				}
			}
		}
	}

	return uf.GetMaxSize()
}

type UnionFind struct {
	parent map[int]int
	size   map[int]int
	maxSize int
}

func NewUnionFind() *UnionFind {
	return &UnionFind{make(map[int]int), make(map[int]int), 0}
}

func (uf *UnionFind) Find(x int) int {
	if _, exists := uf.parent[x]; !exists {
		uf.parent[x] = x
		uf.size[x] = 1
		uf.maxSize = max(uf.maxSize, 1)
	}

	for x != uf.parent[x] {
		x = uf.parent[x]
	}

	return x
}

func (uf *UnionFind) Union(a, b int) {
	fa, fb := uf.Find(a), uf.Find(b)
	if fa != fb {
		sa, sb := uf.size[fa], uf.size[fb]
		big, small := fa, fb
		if sa < sb {
			big, small = fb, fa
		}
		uf.parent[small] = big
		uf.size[big] += uf.size[small]
		uf.maxSize = max(uf.maxSize, uf.size[big])
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}