好的，我们接下来讲解 LeetCode 第 221 题：最大正方形（Maximal Square）。

题目描述

给定一个由 '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（因为存在一个 2x2 的正方形，面积为 4）

解题思路

第一步：暴力法的思考

最直接的想法是：

1. 遍历矩阵中的每一个点 (i, j) 作为正方形的左上角。
2. 对于每个左上角，尝试不同的正方形边长 k，从 1 开始逐渐增大。
3. 检查以 (i, j) 为左上角、边长为 k 的正方形内是否全为 '1'。
4. 记录能得到的最大边长。

这种方法的时间复杂度是 O(m * n * min(m, n)²)，因为要遍历每个左上角，并且对每个左上角可能要检查多个边长，检查一个边长为 k 的正方形需要 O(k²) 时间（可以通过预处理优化到 O(1)，但即使优化后复杂度仍较高）。

第二步：动态规划的直觉

我们希望用更高效的方法。考虑一个正方形右下角的位置 (i, j)：

• 如果 matrix[i][j] = '0'，那么以它为右下角的正方形边长只能是 0。
• 如果 matrix[i][j] = '1'，那么以它为右下角的最大正方形边长，取决于它上方、左方、左上方三个相邻位置所能构成的最大正方形。

具体来说：
设 dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长。
那么状态转移方程为：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

前提是 matrix[i][j] == '1'，否则 dp[i][j] = 0。

第三步：为什么取最小值？

我们通过一个例子来理解：
假设当前 matrix[i][j] = '1'，我们看三个相邻位置：

• dp[i-1][j]：表示上方能形成的最大正方形边长。
• dp[i][j-1]：表示左方能形成的最大正方形边长。
• dp[i-1][j-1]：表示左上方能形成的最大正方形边长。

如果这三个值中最小的是 2，说明：

• 上方和左方都有足够多的连续 '1' 支撑一个更大的正方形。
• 但是左上方那个位置的值限制了我们，因为如果左上方只能形成边长 2 的正方形，那么当前点加入后，最大只能形成边长 3 的正方形。

取最小值是因为正方形的扩张受限于最短的那条边。

第四步：动态规划步骤

1. 初始化一个与 matrix 同大小的 dp 数组，初始值全为 0。
2. 初始化 max_side = 0 记录最大边长。
3. 遍历每个位置 (i, j)：
   • 如果 matrix[i][j] == '1'：
     • 如果 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。
   • 否则 dp[i][j] = 0。
   • 更新 max_side = max(max_side, dp[i][j])。
4. 返回 max_side * max_side（面积）。

第五步：示例推导

对示例矩阵进行推导（dp[i][j] 值）：

矩阵：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

dp 表（只写值）：

1 0 1 0 0
1 0 1 1 1
1 1 1 2 2
1 0 0 1 0

• 第三行第四列 (2,3)：左边是 1，上边是 1，左上角是 1，min(1,1,1)=1，+1 后得 2。
• 第三行第五列 (2,4)：左边是 2，上边是 1，左上角是 1，min(2,1,1)=1，+1 后得 2。
• 最大边长为 2，面积 = 4。

第六步：复杂度分析

• 时间复杂度：O(m * n)，遍历整个矩阵一次。
• 空间复杂度：O(m * n)（可以优化到 O(n) 甚至 O(1) 如果允许修改原矩阵）。

总结

这道题的关键是定义 dp[i][j] 为以 (i, j) 为右下角的最大正方形边长，然后利用相邻三个位置的 dp 值进行状态转移。这种方法比暴力法高效很多，是典型的二维动态规划应用。