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

题目描述

在一个由 '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. 遍历矩阵中的每个元素。
2. 如果该元素是 '1'，则将其作为正方形的左上角。
3. 尝试扩展正方形的边长，检查新增的一行一列是否全为 '1'。
4. 记录能扩展到的最大边长。

这种方法时间复杂度高，为 O(m²n²)（m、n 为矩阵尺寸），在较大矩阵时会超时。

第二步：动态规划的思路

我们可以用 动态规划 来优化。定义：

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

为什么是右下角？
因为一个正方形由其右下角位置和边长唯一确定，这样我们可以利用之前的结果来递推。

第三步：递推关系推导

考虑 dp[i][j] 的值如何由之前的状态得到：

• 如果 matrix[i][j] == '0'，那么以它为右下角的正方形不存在，dp[i][j] = 0。
• 如果 matrix[i][j] == '1'：
  • 它自己可以构成边长 1 的正方形。
  • 如果它的 左边 (i, j-1)、上边 (i-1, j)、左上角 (i-1, j-1) 也都是一个正方形的右下角，那么它可以扩展成更大的正方形。

具体来说：
dp[i][j] 的值取决于它左边、上边、左上角三个位置的最小值，因为正方形需要这三个方向都满足条件：

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

为什么是最小值？

• dp[i-1][j] 表示上方能形成的最大正方形边长。
• dp[i][j-1] 表示左方能形成的最大正方形边长。
• dp[i-1][j-1] 表示左上方能形成的最大正方形边长。
• 木桶效应：以 (i,j) 为右下角的正方形边长受限于这三个方向中最短的那一块，否则无法构成全部为 1 的正方形。

第四步：动态规划步骤

1. 初始化一个与 matrix 同尺寸的 dp 数组，初始值可设为 0。
2. 遍历矩阵的每个位置 (i, j)：
   • 如果 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。
3. 在遍历过程中记录最大的 dp[i][j] 值，记为 maxSide。
4. 返回面积为 maxSide * maxSide。

第五步：举例说明

以题目示例：

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) 位置，左边 dp[2][2]=1，上边 dp[1][3]=1，左上 dp[1][2]=1，最小值 1，加 1 得 2。
• 在 (2,4) 位置，左边 dp[2][3]=2，上边 dp[1][4]=1，左上 dp[1][3]=1，最小值 1，加 1 得 2。
• 最大边长为 2，面积 4。

第六步：代码实现（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)]
    maxSide = 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] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                if dp[i][j] > maxSide:
                    maxSide = dp[i][j]
    
    return maxSide * maxSide

第七步：复杂度分析

• 时间复杂度：O(mn)，遍历整个矩阵一次。
• 空间复杂度：O(mn)，用于存储 dp 数组。可以优化到 O(n)（只保留上一行和当前行），但思路不变。

这个题目是动态规划在二维矩阵中的经典应用，关键在于定义状态和找到递推关系。