题目重点：四邻接遍历完整矩阵，再解释只保留行前沿的连通分量封口与面积累积。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 示例完整矩阵，不修改输入，空矩阵或零列返回(0,0)。
- 四邻接且只含0/1；流式追问是只读一次、知道每行宽度且不能回看旧行。
解题路线
- 完整矩阵遍历每个未访问1作为新岛起点，用栈探索全部四邻1并计area，完成后更新largest。发现时就标seen，避免多父节点重复入栈。
- 每次探索恰覆盖一个连通分量，起点计一次岛；所有1迟早被发现且只计面积一次，得到count和max。用显式栈避免蛇形长岛递归深度爆掉。
- 逐行输入可只保留前一行与当前行标签、活跃分量的并查集与累计面积。当前1与左/上1合并，合并时只累加各root面积一次。
- 处理完整行后，上一前沿root若在当前行没有任何代表，就不可能与未来行连接：未来四邻路径必须穿越当前行。将它封口，count+1并更新largest；最终加一空行flush。
- 面积是分量累计，不是当前行1个数。为了O(width)内存，每行把当前活跃root压缩重编号、丢弃封口root和旧节点，不能不断追加DSU节点又声称只存两行。
- 如果要输出岛屿所有坐标或按原图返回label矩阵，输出本身O(RC)，与只求计数/最大面积的流式合同不同。
手动走一遍
训练[[1,0,1],[1,1,0]]有2岛，最大面积3。流式前两列分量可跨下一行连通；只有一行完全失去代表后才能确定封口。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def islands_and_largest(grid):
"""Non-mutating, four-neighbor 0/1 rectangular grid."""
if not grid:
return 0,0
width=len(grid[0])
if any(len(row)!=width for row in grid) or any(v not in (0,1) for row in grid for v in row):
raise ValueError("expected rectangular binary grid")
seen=set()
count=largest=0
for r,row in enumerate(grid):
for c,value in enumerate(row):
if not value or (r,c) in seen:continue
count+=1
stack=[(r,c)]
seen.add((r,c))
area=0
while stack:
x,y=stack.pop()
area+=1
for nx,ny in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):
if 0 <= nx < len(grid) and 0 <= ny < width and grid[nx][ny] and (nx,ny) not in seen:
seen.add((nx,ny))
stack.append((nx,ny))
largest=max(largest,area)
return count,largest
复杂度
完整示例O(RC)时间、O(RC)seen/stack；严格回收的前沿DSU方案约O(RC·α(C))时间、O(C)状态，不含不可避免的额外输出。
易错点与追问
容易失分的边界
- 只按每行段数累加，漏跨行合并。
- 分量合并面积重复累加。
- 流式DSU不回收却称O(C)。
继续深挖
- 对角也连通时前沿检查怎样扩展？
- 同时统计岛屿周长怎么做？
- 未来允许回补历史行时封口为何不可靠？
