Meta 岛屿大小查询API：预处理到常数查询

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 0海/1陆，四方向连通；对角相邻不连。网格静态，查询不修改。面积按陆格数量。
• 目标是“恰好面积存在”，不是岛数、最大面积或翻转一个0后的最大岛。size<=0均不存在。

解题路线

1. 遍历所有陆地，尚未访问则DFS/BFS完成整个分量，count每个格一次。结束该分量后再把count加入sizes集合。
2. 不能在DFS中途将当前累积count加入集合，因为中途面积不代表完整岛。例如面积5的岛不应因此让size1/2/3/4都true。
3. 构造时一次扫描预计算所有完整面积，isSizeExist只查set；面积重复无需记录计数，若以后需多少个岛改Counter。

手动走一遍

[[1,1,0],[0,1,0],[0,0,1]]四邻形成面积3和1，查询3/1为true，2/0为false；右下1与中间1对角相邻不连。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class IslandSizeIndex:
    """Static 0/1 matrix; FOUR-neighbor adjacency; does not mutate the matrix."""
    def __init__(self,grid):
        self.sizes=set()
        if not grid:return
        h,w=len(grid),len(grid[0])
        if any(len(row)!=w for row in grid) or any(v not in (0,1) for row in grid for v in row):
            raise ValueError('rectangular binary matrix required')
        seen=set()
        for r in range(h):
            for c in range(w):
                if grid[r][c]!=1 or (r,c) in seen:continue
                stack=[(r,c)];seen.add((r,c));count=0
                while stack:
                    rr,cc=stack.pop();count+=1
                    for dr,dc in ((-1,0),(1,0),(0,-1),(0,1)):
                        nr,nc=rr+dr,cc+dc
                        if 0<=nr<h and 0<=nc<w and grid[nr][nc]==1 and (nr,nc) not in seen:
                            seen.add((nr,nc));stack.append((nr,nc))
                self.sizes.add(count)
    def is_size_exist(self,size):return size in self.sizes

复杂度

预处理O(HW)时间/O(HW)visited最坏空间，面积集合最多O(numberOfIslands)；每次查询预期O(1)。独立DSU分量计数验证而非另一份同样DFS。

易错点与追问

容易失分的边界

• 把set.add(count)放遍历内部会将临时面积错误当完整岛。
• 无visited或出队才标记会使同格多次入队并重复计数。

继续深挖

• 若陆地动态新增，用DSU与面积频次维护：union先减旧size频率再加新size；删除陆地会拆分，普通DSU不能直接处理。
• 若允许八方向连通，替换邻接并重新构造索引，现有sizes不可沿用。