Meta Toeplitz矩阵：相邻对角检查与流式行

题意与假设

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

• 输入矩形矩阵，空矩阵或零列视为满足；单行单列天然满足。ragged矩阵拒绝。
• 相等比较按元素类型的合同，示例整数；浮点近似相等需要明确容差及传递性问题。

解题路线

1. 对每个r>=1/c>=1，检查matrix[r][c]==matrix[r−1][c−1]。每条对角是这些相邻关系的链，相等传递保证整条一致。
2. 不需把全部对角值建立map；矩阵可随机访问时只要两层遍历和常数状态。发现任一不等立即false。
3. 流式按行读取只能保留上一行，当前行从第1列与prev前一列比；行宽O(C)空间。若磁盘块而不是行，需保留跨块边界的对角信息。

手动走一遍

[[1,2,3],[4,1,2],[5,4,1]]满足；把最后1改为9后(2,2)与(1,1)不等即false。

Python 参考实现

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

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

def is_toeplitz(matrix):
    if not matrix:
        return True
    if any(len(row) != len(matrix[0]) for row in matrix):
        raise ValueError("rectangular matrix required")
    return all(matrix[r][c] == matrix[r-1][c-1] for r in range(1,len(matrix)) for c in range(1,len(matrix[0])))

复杂度

O(RC)时间，随机访问输入O(1)辅助空间；行流式O(C)空间，不含输入/输出。

易错点与追问

容易失分的边界

• 只查主对角会漏掉其他对角；每个非首行首列单元都要检查。
• row0/col0没有左上邻居，不应因缺邻居判失败。

继续深挖

• 若只允许一次读取且内存不足一整行，说明外存块与边界保存策略，不能仍声称常数内存。
• 修改一个元素后如何快速维护Toeplitz状态？更新它与左上及右下两条相邻比较的违规计数。