221. 最大正方形

题目链接（中等）

题目描述

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

数据范围：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

示例

示例 1：

输入：

matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

输出： 4

示例 2：

输入： matrix = [["0","1"],["1","0"]]
输出： 1

示例 3：

输入： matrix = [["0"]]
输出： 0

核心思路

找到矩阵中只包含 '1' 的最大正方形，返回其面积。

面积 = 边长 × 边长，所以问题等价于：找到最大的边长。

两种做法：

• 暴力枚举：以每个 '1' 为左上角，逐层向外扩张，检查新增的行列是否全是 '1'；
• 动态规划：定义 dp[i][j] 为「以 (i, j) 为右下角的最大全 1 正方形边长」，用状态转移方程一次遍历搞定。

---

方法一：暴力枚举

思路及解法

对矩阵中每个 '1'，以它为左上角，尝试扩展到最大可能的正方形：

1. 计算可能的最大边长 currentMaxSide = min(rows - i, columns - j)；
2. 从边长 k = 1 开始，逐层扩展，每次检查新增的一行一列是否全是 '1'；
3. 如果新增行 / 列中遇到 '0'，当前正方形不合法，停止扩展；
4. 否则边长 +1，继续尝试；
5. 记录全局最大边长 maxSide，最后返回 maxSide²。

优点：思路直观，容易想到。 缺点：复杂度高，每扩展一层都要检查一行一列。

代码

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        max_side = 0

        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '1':
                    max_side = max(max_side, 1)
                    current_max = min(rows - i, cols - j)

                    for k in range(1, current_max):
                        # 检查新增的行和列是否全为 '1'
                        flag = True
                        if matrix[i + k][j + k] == '0':
                            break
                        for m in range(k):
                            if matrix[i + k][j + m] == '0' or matrix[i + m][j + k] == '0':
                                flag = False
                                break
                        if flag:
                            max_side = max(max_side, k + 1)
                        else:
                            break

        return max_side * max_side

复杂度分析

• 时间复杂度：$O(mn \cdot \min(m, n)^2)$，每个 '1' 最多扩展 $\min(m, n)$ 层，每层检查 $O(\min(m, n))$ 个元素。
• 空间复杂度：$O(1)$。

---

方法二：动态规划（推荐）

思路及解法

定义 dp[i][j] 为「以 (i, j) 为右下角、且只包含 '1' 的正方形的最大边长」。

转移思路：

• 若 matrix[i][j] == '0'，则 dp[i][j] = 0（右下角是 0，无法构成正方形）；
• 若 matrix[i][j] == '1'：
  • 若 i == 0 或 j == 0（第一行或第一列），最大边长只能是 1；
  • 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

为什么取三个邻居的最小值加 1？

以 (i, j) 为右下角、边长为 k 的正方形，要求：

• 左上角的子正方形（边长 k-1）必须全为 1 → dp[i-1][j-1] ≥ k-1；
• 正上方那一列必须全为 1 → dp[i-1][j] ≥ k-1；
• 正左方那一行必须全为 1 → dp[i][j-1] ≥ k-1。

三者同时满足才能扩展成边长 k 的正方形，所以取三者的最小值再 +1。

直觉理解：(i, j) 能形成的正方形边长，受限于「左边、上边、左上角」三个位置能形成的正方形边长中最小的那个，再往外扩一格。

例子：

原始矩阵：              dp：
0 1 1 1 0              0 1 1 1 0
1 1 1 1 0              1 1 2 2 0
0 1 1 1 1    →         0 1 2 3 1
0 1 1 1 1              0 1 2 3 2
0 0 1 1 1              0 0 1 2 3

最大 dp 值是 3，所以最大正方形面积是 9。

遍历过程中实时更新最大边长，最后返回 max_side²。

代码

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * cols for _ in range(rows)]
        max_side = 0

        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    max_side = max(max_side, dp[i][j])

        return max_side * max_side

复杂度分析

• 时间复杂度：$O(mn)$，每个元素计算一次。
• 空间复杂度：$O(mn)$，dp 数组和矩阵同大小。

---

方法三：动态规划 + 滚动数组（$O(n)$ 空间）

思路及解法

dp[i][j] 只依赖上一行和本行左侧的信息，可以压成一维数组：

• dp[j] 更新前是 dp[i-1][j]（上一行同列）；
• dp[j-1] 更新后是 dp[i][j-1]（本行左列）；
• 需要一个 prev 变量保存 dp[i-1][j-1]（左上角）。

更新顺序：从左到右遍历 j，用一个 temp 暂存更新前的 dp[j]（即上一行的值），作为下一轮的 prev。

代码

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        dp = [0] * cols
        max_side = 0

        for i in range(rows):
            prev = 0                          # dp[i-1][j-1]
            for j in range(cols):
                temp = dp[j]                  # 暂存 dp[i-1][j]
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[j] = 1
                    else:
                        dp[j] = min(dp[j], dp[j-1], prev) + 1
                    max_side = max(max_side, dp[j])
                else:
                    dp[j] = 0
                prev = temp                   # 本轮 dp[j] 作为下一轮的左上角

        return max_side * max_side

复杂度分析

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(n)$，只保留一行。

---

三种方法对比

方法	时间	空间	特点
暴力枚举	$O(mn \cdot \min(m, n)^2)$	$O(1)$	思路简单，但太慢
DP（二维）	$O(mn)$	$O(mn)$	标准解法，状态清晰
DP（滚动数组）	$O(mn)$	$O(n)$	空间最优，面试推荐

推荐：

• 面试：写方法二（二维 DP），思路清晰、状态定义明确；
• 进阶：补一句「可以滚动数组优化到 $O(n)$ 空间」，展示空间优化意识。

---

关键细节

1. dp[i][j] 的定义

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

注意是「右下角」，不是「左上角」也不是「中心」。定义对了，转移才顺。

2. 边界条件

第一行和第一列，如果 matrix[i][j] == '1'，dp[i][j] = 1（只能形成 1×1 的正方形）。

3. 取 min 的原因

三个邻居分别代表：

• dp[i-1][j-1]：左上方的最大子正方形；
• dp[i-1][j]：正上方；
• dp[i][j-1]：正左方。

只有三者都足够大，(i, j) 才能扩出更大的正方形。取三者最小值就是「瓶颈」。

4. max_side 边遍历边更新

不需要最后再遍历 dp 数组求最大值，遍历中实时更新即可，省一次遍历。

5. 与「统计全为 1 的正方形子矩阵」（LC 1277）的关系

LC 1277 要求「统计所有全 1 子正方形的个数」，转移方程与本题完全相同，只需要把 dp[i][j] 累加即可。两题可以一起做，加深理解。

---

总结

• 状态定义：dp[i][j] = 以 (i, j) 为右下角的最大全 1 正方形边长；
• 转移方程：
  • matrix[i][j] == '0' → dp[i][j] = 0；
  • i == 0 或 j == 0 → dp[i][j] = 1；
  • 否则 → dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1；
• 答案：max(dp)²；
• 空间优化：滚动数组，一维数组 + prev 变量，空间降到 $O(n)$；
• 核心直觉：能形成多大正方形，取决于左、上、左上三个方向中「最小的那个」。

相关题目

• LC 1277. 统计全为 1 的正方形子矩阵（同一个转移方程，统计数量）
• LC 85. 最大矩形（从正方形扩展到矩形，用单调栈）
• LC 304. 二维区域和检索（二维前缀和）