Salesforce Maximal Square：从暴力边长枚举到一维 DP

题意与假设

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

• 输入是矩形字符矩阵，只含 '0' 和 '1'；空矩阵或零列返回 0，非矩形或其他字符在训练代码中拒绝。
• 正方形必须轴对齐且边长至少为 1，返回面积而非边长或位置；单个 '1' 的答案为 1。
• 若面试平台传数字 0/1，可在入口转换或改比较方式；这里按题目的字符 '1' 描述实现。

解题路线

1. 暴力法可枚举每个左上角与边长并检查方块内所有元素；候选很多且重复检查，最坏可到 O(RC·min(R,C)^3) 的粗上界，面试时应说明可通过前缀和把单次全 1 检查降至 O(1)。
2. 最优 DP 令 dp[r][c] 为以 (r,c) 作右下角的最大全 1 正方形边长。若当前为 0，则为 0；若为 1，则等于 1+min(上、左、左上)。三个邻居都至少有边长 s 时才可扩成 s+1，否则短边决定上限。
3. 按行滚动只存上一行 dp；更新当前列前把旧 dp[c] 保存作下一列的左上角 diagonal。逐格记录最大边长，最终平方得到面积。

手动走一遍

矩阵 [[1,1,0],[1,1,1],[0,1,1]]（代码输入为字符）中，左上 2×2 全为 1，边长 2、面积 4。右下角虽然自身为 1，但其上、左、左上若任一不能支撑边长 2，就不能形成 3×3；取三者最小值避免误报。全零矩阵返回 0。

Python 参考实现

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

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

def maximal_square_area(matrix: list[list[str]]) -> int:
    """Area of the largest all-'1' axis-aligned square."""
    if not matrix:
        return 0
    cols = len(matrix[0])
    if any(len(row) != cols for row in matrix):
        raise ValueError("matrix must be rectangular")
    dp = [0] * (cols + 1)
    best_side = 0
    for row in matrix:
        diagonal = 0
        for col, value in enumerate(row, start=1):
            above = dp[col]
            if value == "1":
                dp[col] = 1 + min(dp[col - 1], above, diagonal)
                best_side = max(best_side, dp[col])
            elif value == "0":
                dp[col] = 0
            else:
                raise ValueError("matrix values must be '0' or '1'")
            diagonal = above
    return best_side * best_side

复杂度

R 行、C 列。DP 逐格一次，时间 O(RC)，辅助空间 O(C)；若存完整二维表则空间 O(RC)。暴力前缀和改进法也需枚举 O(RC·min(R,C)) 个候选，仍慢于 DP。

易错点与追问

容易失分的边界

• 只看上与左而漏掉左上，L 形全 1 会被误判成完整方块。
• 把最大边长直接返回，忘记题目要求面积。
• 一维滚动时先覆盖 dp[c] 再读取旧值作 diagonal，递推引用错行。
• 把相邻的 Maximal Rectangle 与本题合并：矩形可长宽不同，需要另一套柱状图方法。

继续深挖

• 若要返回所有最大正方形坐标，保留达到最大边长时的右下角；同分顺序先约定。
• 若矩阵动态翻转单个格子，局部 DP 值可能向右下传播，需分析更新区域而非承诺 O(1)。
• 若只是判断是否存在边长至少 K 的全 1 方块，可用前缀和 O(RC) 建表后 O(RC) 扫描候选。