最大正方形

这是一道围绕算法展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

算法

题目分析

这道题表面上是在处理「最大正方形」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考算法这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：以每个格子作为正方形右下角，边长取决于它上方、左方和左上方三个状态的最小值。

推荐代码

推荐解法：动态规划

时间复杂度： O(mn)

空间复杂度： O(mn)

核心思路：以每个格子作为正方形右下角，边长取决于它上方、左方和左上方三个状态的最小值。

class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxSide = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    if (row == 0 || col == 0) {
                        dp[row][col] = 1;
                    } else {
                        dp[row][col] = Math.min(
                            Math.min(dp[row - 1][col], dp[row][col - 1]),
                            dp[row - 1][col - 1]
                        ) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[row][col]);
                }
            }
        }

        return maxSide * maxSide;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用动态规划，状态定义为“以当前格子为右下角的最大正方形边长”。

核心过程

如果当前位置是 0，那边长就是 0。
如果是 1，就看上、左、左上三个位置各自能撑多大。
当前边长取这三个值的最小值再加 1。
遍历中维护最大边长，最后平方得到面积。

复杂度总结

时间复杂度 O(mn)，空间复杂度 O(mn)。

面试补一句：这题真正的关键是把状态定义成“右下角边长”，不是面积。

核心思路

这题不是看当前位置能不能放一个 1，而是问“以它为右下角，最大的全 1 正方形边长是多少”。只要把这个状态定义对，转移式会非常自然。

步骤讲解

定义右下角状态

dp[i][j] 表示以 (i,j) 为右下角的最大全 1 正方形边长。

为什么这样做：右下角状态能把局部扩展关系表达得最清楚。

对应代码提示：int[][] dp = new int[rows][cols];

根据三个相邻状态转移

若当前位置是 1，则边长等于上、左、左上三个状态最小值再加 1。

为什么这样做：只要有一边短，能扩成的正方形就会被那条短边限制。

对应代码提示：dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;

记录最大边长并换算面积

遍历过程中维护最大边长，最后返回其平方。

为什么这样做：题目要的是面积，不是边长。

对应代码提示：answer = Math.max(answer, dp[i][j]);

易错点

把三个相邻状态取最大值

那样会高估能扩展出的正方形边长。

正确理解：必须取最小值，因为最短边决定上限。

忘记边界格子单独处理

第一行和第一列没有完整的三个前驱状态。

正确理解：边界上只要当前位置是 1，边长就是 1。

复杂度与适用判断

时间复杂度：O(mn)

空间复杂度：O(mn)

比其他方案更好在哪里：比暴力枚举所有正方形再检查内部元素高效得多。

适用判断：当某个二维结构能由左、上、左上三个方向递推时，二维 DP 通常是首选。

额外提醒

正方形能否扩一圈，取决于三个相邻位置里最短的那一个。