vvrf / DSA.log

问题拆解

在一个只含 '0' 和 '1' 的矩阵里，找出只包含 '1' 的最大正方形，返回其面积。

暴力做法是枚举每个格子作为左上角，再枚举边长逐圈验证全 1，最坏 O(m·n·min(m,n)²) 起步，矩阵稍大就吃不消。它慢在每个正方形都从零验证，完全没有复用“小正方形已经成立”这个信息。

换个锚点：给每个格子 (i, j) 定义 dp[i][j] 为“以它为右下角的全 1 正方形的最大边长”。想以 (i, j) 为右下角撑起一个边长为 k 的正方形，需要三个条件同时成立：左邻居能撑起 k-1（补齐左侧列以外的部分）、上邻居能撑起 k-1、左上邻居能撑起 k-1（补齐对角方向）。三者缺一不可，所以：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1   （当 grid[i][j] == '1'）

这就是木桶短板的直觉：三个方向里任何一个短了，大正方形就在那个方向上缺一角，边长被最短的那块板压住。格子本身是 '0' 时 dp 直接为 0。

把“找最大正方形”改写成“以每个格子为右下角能撑多大”，全局最优就变成了逐格转移的局部问题——固定一个角是很多形状类 DP 的破题动作。

二维 DP 取三邻居最小值

首行首列的格子没有完整的三个邻居，以它们为右下角的正方形边长至多是 1（自己是 '1' 就是 1）。为了不写特判，给 dp 表在上方和左方各垫一圈 0：dp 开成 (m+1) × (n+1)，dp[i+1][j+1] 对应格子 (i, j)，哨兵圈的 0 会让边界格子的 min 自动算出 1。

public int maximalSquare(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1]; // 多垫一圈 0，免去边界特判
    int best = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                // 左、上、左上三块短板取最小
                dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
                best = Math.max(best, dp[i + 1][j + 1]);
            }
        }
    }
    return best * best; // 返回面积
}

def maximalSquare(matrix: List[List[str]]) -> int:
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # 多垫一圈 0，免去边界特判
    best = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == "1":
                # 左、上、左上三块短板取最小
                dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1
                best = max(best, dp[i + 1][j + 1])
    return best * best  # 返回面积

func maximalSquare(matrix [][]byte) int {
    m, n := len(matrix), len(matrix[0])
    dp := make([][]int, m+1) // 多垫一圈 0，免去边界特判
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    best := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == '1' {
                // 左、上、左上三块短板取最小
                dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
                best = max(best, dp[i+1][j+1])
            }
        }
    }
    return best * best // 返回面积
}

pub fn maximal_square(matrix: Vec<Vec<char>>) -> i32 {
    let (m, n) = (matrix.len(), matrix[0].len());
    let mut dp = vec![vec![0i32; n + 1]; m + 1]; // 多垫一圈 0，免去边界特判
    let mut best = 0;
    for i in 0..m {
        for j in 0..n {
            if matrix[i][j] == '1' {
                // 左、上、左上三块短板取最小
                dp[i + 1][j + 1] = dp[i][j + 1].min(dp[i + 1][j]).min(dp[i][j]) + 1;
                best = best.max(dp[i + 1][j + 1]);
            }
        }
    }
    best * best // 返回面积
}

两个容易栽的细节：一是题目给的是字符矩阵，判断要写 == '1' 而不是 == 1；二是题目要的是面积，dp 里存的是边长，最后别忘了平方。另外要理解为什么 min 里必须带上左上角 dp[i-1][j-1]：只看左和上，0 1 / 1 1 这种缺左上角的形状会被误判成边长 2——左、上各自的正方形拼起来并不能保证对角那块也是实心的。

这张表同样可以压成一维滚动数组（dp[i-1][j-1] 用一个临时变量在覆盖前存下来），空间降到 O(n)；这里保留二维写法，是因为三邻居的几何含义在二维表上一眼可见，更值得先看懂。

复杂度

指标	复杂度	原因
时间	`O(m × n)`	每个格子转移一次，转移是常数次比较
空间	`O(m × n)`	dp 表；用滚动数组可降到 O(n)

可以迁移的模式

形状类问题先固定一个基准点（这里是右下角），把“找全局形状”化成“每个点撑多大”的逐点子问题；
多个前置条件同时约束规模时用 min 转移——短板决定整体，这正是木桶原理的 DP 形态；
dp 表外垫一圈哨兵 0，让首行首列的转移和内部格子走同一条公式，消灭边界特判。

把“正方形”换成“只含 1 的矩形”，min 转移就不够用了，那是单调栈的地盘（85 题最大矩形）——对比着做能看清 DP 适用的边界。