最大正方形
题目描述
解题思路
这是一个经典的 二维动态规划（2D DP）问题，通常称为 “最大正方形”（Maximal Square）。
✅ 问题分析
我们要在由 '0' 和 '1' 组成的矩阵中，找到全为 '1' 的最大正方形，并返回其面积（即边长的平方）。
关键点：
- 正方形必须连续且全为
'1'。 - 返回的是面积，但我们可以先求最大边长，再平方。
✅ 动态规划思路
状态定义：
设 dp[i][j] 表示 以 (i, j) 为右下角的最大正方形的边长。
为什么选“右下角”？因为这样可以利用左、上、左上三个方向的信息来扩展正方形。
状态转移：
- 如果
matrix[i][j] == '0'，则无法形成全'1'正方形 →dp[i][j] = 0 - 如果
matrix[i][j] == '1'，则：解释：当前点能扩展成多大的正方形，受限于三个邻居中最小的那个（木桶效应）。dp[i][j] = 1 + min( dp[i-1][j], # 上方 dp[i][j-1], # 左方 dp[i-1][j-1] # 左上方 )
初始化：
- 第一行和第一列：若
matrix[i][j] == '1'，则dp[i][j] = 1 - 可以在主循环中通过判断
i == 0 or j == 0处理，也可以提前初始化。
答案：
- 遍历过程中记录
max_side = max(max_side, dp[i][j]) - 最终返回
max_side * max_side
✅ Python 代码实现
def maximalSquare(matrix):
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
max_side = max(max_side, dp[i][j])
# else: dp[i][j] 保持为 0
return max_side * max_side
✅ 示例验证
# 示例 1
matrix1 = [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
print(maximalSquare(matrix1)) # 输出: 4
# 示例 2
matrix2 = [["0","1"],["1","0"]]
print(maximalSquare(matrix2)) # 输出: 1
# 示例 3
matrix3 = [["0"]]
print(maximalSquare(matrix3)) # 输出: 0
全部符合预期。
⏱️ 复杂度分析
- 时间复杂度：O(m × n)，每个格子访问一次。
- 空间复杂度：O(m × n)，用于 DP 表。
可进一步优化空间至 O(n)（只保存上一行），但本题
m, n ≤ 300，无需优化。
✅ 关键启发（与 LCS 对比）
| 问题 | 状态含义 | 依赖方向 | 核心思想 |
|---|---|---|---|
| LCS | 两个序列前缀的匹配长度 | 左、上、左上 | 序列对齐 |
| Maximal Square | 以 (i,j) 为右下角的最大正方形边长 | 左、上、左上 | 木桶效应 + 局部扩展 |
虽然都用
min或max和三个方向，但语义完全不同：LCS 是“选择最优路径”，而本题是“受限扩展”。
✅ 此解法简洁高效，是处理矩阵中形状探测类问题的标准 DP 模板之一。
非常好的问题！“最大正方形”（Maximal Square）虽然是一个经典 DP 题，但其中蕴含的细节和思想非常值得深入挖掘。下面从 实现注意事项 和 算法启发 两个维度进行系统总结。
一、代码实现中的注意事项（易错点 & 实践细节）
1. 字符 '1' 与整数 1 的混淆
- 输入矩阵中元素是字符串
'0'和'1'，不是整数。 - ❌ 错误写法：
if matrix[i][j] == 1: - ✅ 正确写法：
if matrix[i][j] == '1':
这是 LeetCode 上高频出错点，尤其在快速编码时容易忽略。
2. 边界条件的处理方式
- 当
i == 0或j == 0（第一行或第一列）时，无法访问dp[i-1][j-1]等。 - 解决方案有两种：
- 方案 A：在循环内判断
if i == 0 or j == 0: dp[i][j] = 1 - 方案 B：创建
(m+1) x (n+1)的 DP 表，从i=1, j=1开始遍历，避免越界。
- 方案 A：在循环内判断
✅ 推荐方案 A（更直观），但需确保逻辑覆盖所有边界。
3. DP 表初始化为 0 是安全的
- 因为
'0'对应的dp[i][j]就是 0，无需额外赋值。 - 所有
'1'的位置会在主循环中被正确更新。
这种“懒初始化”简化了代码，但前提是状态转移逻辑覆盖所有情况。
4. 不要忘记更新全局最大值
dp[i][j]只表示以(i,j)为右下角的正方形边长。- 最终答案是所有
dp[i][j]中的最大值的平方。 - ❌ 常见错误：直接返回
dp[m-1][n-1] ** 2（只考虑右下角）。
✅ 必须在循环中维护 max_side = max(max_side, dp[i][j])。
5. 空输入的防御性检查
- 虽然题目保证
m, n ≥ 1，但在实际工程或面试中，建议加：if not matrix or not matrix[0]: return 0 - 体现代码鲁棒性。
6. 空间优化的可能性（进阶）
- 由于
dp[i][j]只依赖上一行和当前行的左侧值，可用滚动数组优化到 O(n) 空间：prev = [0] * n curr = [0] * n for i in range(m): for j in range(n): if matrix[i][j] == '1': if i == 0 or j == 0: curr[j] = 1 else: curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1]) max_side = max(max_side, curr[j]) else: curr[j] = 0 prev, curr = curr, [0] * n # 或复用 curr 并清零 - 在内存敏感场景有用，但本题无需。
二、由本题得到的算法启发
1. “以某点为右下角”是矩阵形状问题的经典状态设计
- 类似思路也用于：
- 最大矩形（需结合柱状图 + 单调栈）
- 全 1 子矩阵计数
- 岛屿问题中的局部结构分析
- 核心思想：将全局问题分解为每个位置作为“终点”的局部问题。
✅ 启发：遇到“最大/最小形状”问题，优先考虑“以 (i,j) 为角点”的状态定义。
2. 木桶原理在 DP 中的体现
- 当前正方形边长受限于 上、左、左上 三个方向的最小值。
- 这是因为要形成边长为
k的正方形，三个方向都必须至少有k-1的边长。
这是典型的“短板效应”在算法中的应用。
✅ 启发：当多个条件必须同时满足时，状态转移常取 min；当只需满足其一时，常取 max。
3. 与“最大全 1 矩形”的区别
- 正方形：边长相等 → 可用上述 DP，O(mn)
- 矩形：长宽可不同 → 不能直接用此 DP，需对每行构建高度数组 + 单调栈（如 LeetCode 85 题）
✅ 启发：形状约束越强，越可能有高效 DP 解法；约束越弱（如任意矩形），可能需要更复杂的数据结构。
4. DP 状态的“局部性”与“可扩展性”
- 本题的
dp[i][j]是局部最优（以 (i,j) 为右下角），但通过遍历所有位置，可得到全局最优。 - 这体现了 DP 的核心哲学：通过局部最优解的组合，构造全局最优解。
✅ 启发：设计状态时，问自己：“如果我知道周围的信息，我能推出当前位置的最优解吗？”
5. 从暴力到 DP 的思维跃迁
- 暴力解法：枚举所有可能的正方形（O(m²n²)），检查是否全为
'1'。 - DP 解法：利用重叠子问题和最优子结构，将复杂度降至 O(mn)。
✅ 启发：DP 的本质是避免重复计算。当你发现暴力解中有大量重复子问题时，考虑 DP。
6. 与图像处理的联系
- 在计算机视觉中，类似思想用于：
- 检测图像中的方形区域
- 形态学操作（如膨胀、腐蚀）
- 特征提取（如 Haar 特征）
- 虽然实际系统用更高效的方法（如积分图），但 DP 提供了理论基础。
✅ 启发：基础算法往往是高级应用的基石。
总结
| 维度 | 关键点 |
|---|---|
| 实现注意 | 字符比较、边界处理、全局最大值更新、空输入检查 |
| 算法启发 | 右下角状态设计、木桶原理、形状约束与解法复杂度、局部到全局的 DP 思想 |
掌握这些细节和思想，不仅能正确高效地解决“最大正方形”问题，还能迁移到更广泛的矩阵 DP 和形状分析问题中。