链接

一、题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 50

• grid[i][j] 为 0 或 1

二、分析

本题可以采用搜索，或者并查集方式解答。

本文使用并查集。

三、实现

// 并查集
type UnionFind struct {
	parent []int
}

func NewUnionFind(size int) *UnionFind {
	uf := &UnionFind{
		parent: make([]int, size),
	}
	for i := range uf.parent {
		uf.parent[i] = i
	}
	return uf
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	rootx, rooty := uf.Find(x), uf.Find(y)
	if rootx != rooty {
		if rootx < rooty {
			uf.parent[rooty] = rootx
		} else {
			uf.parent[rootx] = rooty
		}
	}
}

func maxAreaOfIsland(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	m, n := len(grid), len(grid[0])
	// 1. 使用并查集合并同组的点
	uf := NewUnionFind(m * n)
	for i := range grid {
		for j := range grid[i] {
			point := i*n + j
			if grid[i][j] == 0 {
				continue
			}
			// 检查他之前的点，上和左，合并
			// up
			if i > 0 && grid[i-1][j] == 1 {
				up := (i-1)*n + j
				uf.Union(up, point)
			}
			// left
			if j > 0 && grid[i][j-1] == 1 {
				left := i*n + j - 1
				uf.Union(left, point)
			}
		}
	}
	// 2. 基于并查集结果，分组，统计最大组
	// root: cnt
	groups := map[int]int{}
	ans := 0
	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] == 0 {
				continue
			}
			point := i*n + j
			root := uf.Find(point)
			groups[root]++
			ans = max(ans, groups[root])
		}
	}
	return ans
}