Uber 动态岛屿：每次加陆地后的数量与最大面积

题意与假设

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

• 本文可运行版本采用 R×C 四邻接网格，初始全水；每次操作仅将一个水格变陆地，返回岛屿数量与最大岛面积。重复加同一格是幂等操作。
• Phone Screen 题目写 modify matrix，但未说明是否可以从陆地改回水；若允许删除，此增量并查集不能正确拆分连通块。
• 无斜向相连；最大面积按岛内陆地格数量定义。若面试从现有矩阵开始，可先扫描原有陆地并依次 add_land 建立状态。

解题路线

1. 为每个格子建 DSU parent 和 size；size=0 表示水。加陆地时先创建大小 1 的岛，count 加一、largest 至少为 1。
2. 检查四个方向相邻陆地，若根不同则按大小合并、count 减一，并更新合并后岛面积的最大值。
3. 重复 add 不做任何状态改变。DSU 路径压缩与按大小合并保证单次近似常数摊还；任一时刻 count/largest 可 O(1) 读取。

手动走一遍

2×2 全水：依次加 (0,0)、(1,1)、(0,1)，返回 (岛数,最大面积) 为 (1,1)、(2,1)、(1,3)。再次加 (0,1) 仍为 (1,3)。

Python 参考实现

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

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

"""Island count and largest component after each water-to-land update."""


class DynamicIslands:
    def __init__(self, rows: int, cols: int):
        if rows <= 0 or cols <= 0:
            raise ValueError("positive grid dimensions required")
        self.rows = rows
        self.cols = cols
        n = rows * cols
        self.parent = list(range(n))
        self.size = [0] * n
        self.count = 0
        self.largest = 0

    def _root(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def _union(self, a: int, b: int) -> None:
        a = self._root(a)
        b = self._root(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.count -= 1
        self.largest = max(self.largest, self.size[a])

    def add_land(self, row: int, col: int) -> tuple[int, int]:
        if not (0 <= row < self.rows and 0 <= col < self.cols):
            raise ValueError("cell outside grid")
        cell = row * self.cols + col
        if self.size[cell]:
            return self.count, self.largest
        self.size[cell] = 1
        self.count += 1
        self.largest = max(self.largest, 1)
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = row + dr, col + dc
            if 0 <= nr < self.rows and 0 <= nc < self.cols:
                neighbor = nr * self.cols + nc
                if self.size[neighbor]:
                    self._union(cell, neighbor)
        return self.count, self.largest

复杂度

每次只检查四邻，DSU 均摊 O(α(RC))；m 次更新总计 O(m α(RC))，空间 O(RC)。若每次全图 BFS 重算，最坏 O(mRC)。

易错点与追问

容易失分的边界

• 同一个新格可能同时接触同一岛的两个边界；合并前须比较根，避免把一个岛的 count 减两次。
• 重复添加已有陆地必须直接返回当前结果，否则会重复增加 count。
• 并查集无法处理陆地删除后的连通块分裂；若原题的 modify 包含 1→0，需离线回滚 DSU/时间线段树或在线重新搜索受影响连通块。

继续深挖

• 若允许删地且所有操作已知，可把每条相邻边的活跃时间段挂到时间线段树上，配合可回滚 DSU 离线回答；复杂度和实现明显增加。
• 若是稀疏超大网格，可用坐标→DSU ID 哈希映射，只为出现过的陆地建节点，空间降为 O(已加陆地数)。