LeetCode 221. 最大正方形
题目描述
题意分析
在由字符
'0'、'1'组成的矩阵中，找出面积最大的全1正方形，返回它的面积。正方形必须由连续的行和列组成，内部每一个格子都要为1，仅边框满足不够。题目要求的是正方形而不是任意矩形，因此宽和高必须相等；返回的是面积而不是边长。矩阵的行数和列数可以不同，如果没有任何
1，答案为0。
解法：二维动态规划
核心思路
[!blue]
每个正方形都有唯一的右下角。定义
dp[i][j]为以matrix[i - 1][j - 1]为右下角的全1正方形的最大边长，这样只要求出所有格子的状态，再取最大边长的平方，就能覆盖任意位置的答案。当前格为
'0'时，不可能作为任何全1正方形的右下角，状态为0。当前格为'1'时，可以尝试把附近更小的正方形扩成更大的一块。若当前右下角能形成边长
k的正方形，则内部以上方、左方、左上方三个相邻格为右下角，都必然包含边长k - 1的全1正方形，因此三个状态都至少为k - 1。任何一处不足都会留下缺口，所以新的边长不能超过这三个状态的最小值加1。反过来，设三个状态的最小值为
t。以它们为右下角、边长均取t的三个全1正方形，能够覆盖目标区域中除当前格之外的所有位置；当前格又是1，就确实能拼出边长t + 1的完整正方形。因此上界可以达到，递推为dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1。在状态表前面补一行、一列
0，表示矩阵外没有可扩展的正方形，第一行和第一列也能使用相同递推。按从上到下、从左到右的顺序填表，依赖的三个状态都已算出。
解题步骤
- 创建
(m + 1) × (n + 1)的全零状态表，初始化最大边长为0。- 按行遍历原矩阵。当前格为
'0'时，状态保持为0。- 当前格为
'1'时，取上、左、左上三个状态的最小值加1，作为当前最大边长。- 用当前边长更新全局最大值，最后返回最大边长的平方。
代码实现
class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
int columns = matrix[0].length;
int[][] dp = new int[rows + 1][columns + 1];
int maxSide = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= columns; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}
func maximalSquare(matrix [][]byte) int {
rows, columns := len(matrix), len(matrix[0])
dp := make([][]int, rows+1)
for i := range dp {
dp[i] = make([]int, columns+1)
}
maxSide := 0
for i := 1; i <= rows; i++ {
for j := 1; j <= columns; j++ {
if matrix[i-1][j-1] == '1' {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
maxSide = max(maxSide, dp[i][j])
}
}
}
return maxSide * maxSide
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子只计算一次。
- 空间复杂度：$O(mn)$，保存每个位置对应的边长状态。
关键点总结
[!green]
- 固定右下角，让每个局部状态有明确范围，也让所有可能的正方形都有对应状态。
- 三个方向共同保证内部没有缺口，所以取最小值，不能只检查两条边。
- 递推保存边长，全局答案再把最大边长转换成面积。
解法：一维动态规划
核心思路
[!blue]
二维递推只依赖上方、左方和左上方三个状态，因此不必保留整张表，可以逐行覆盖同一个数组。状态的含义仍是“以当前格为右下角的最大正方形边长”，只改变存储方式。
处理第
i行第j列时，dp[j]尚未更新，是上方旧值；dp[j - 1]已经更新，是当前行左方新值；额外变量leftTop保存已经被覆盖的旧左上值。当前格为'1'时，仍取这三个值的最小值加1；为'0'时，当前边长只能为0。每列开始先保存
top = dp[j]，再更新当前格，最后执行leftTop = top。下一列的左上角恰好就是本列原来的上方值，因此这个保存顺序不能颠倒。数组多出的第
0项始终为0，每行开始也把leftTop设为0，分别模拟矩阵左边和左上方的空边界。所有行处理过程中持续记录最大边长，最终返回它的平方。
解题步骤
- 创建长度为列数加
1的全零数组，初始化maxSide = 0。- 逐行遍历，每行先令
leftTop = 0，列下标从1开始，矩阵位置对应matrix[i - 1][j - 1]。- 先保存
top = dp[j]。当前字符为'1'时，用三个相邻状态的最小值加1更新dp[j]，并更新最大边长；否则令dp[j] = 0。- 将
leftTop更新为保存的top，继续处理下一列。- 全部处理后返回
maxSide * maxSide。
代码实现
class Solution {
public int maximalSquare(char[][] matrix) {
int columns = matrix[0].length;
int[] dp = new int[columns + 1];
int maxSide = 0;
for (int i = 1; i <= matrix.length; i++) {
int leftTop = 0;
for (int j = 1; j <= columns; j++) {
// 覆盖前保存上一行同列，下一列仍需要它作为旧左上角。
int top = dp[j];
if (matrix[i - 1][j - 1] == '1') {
dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), leftTop) + 1;
maxSide = Math.max(maxSide, dp[j]);
} else {
// 当前格是零，不能延续上一行的正方形边长。
dp[j] = 0;
}
leftTop = top;
}
}
return maxSide * maxSide;
}
}
func maximalSquare(matrix [][]byte) int {
columns := len(matrix[0])
dp := make([]int, columns+1)
maxSide := 0
for i := 1; i <= len(matrix); i++ {
leftTop := 0
for j := 1; j <= columns; j++ {
// 覆盖前保存上一行同列，下一列仍需要它作为旧左上角。
top := dp[j]
if matrix[i-1][j-1] == '1' {
dp[j] = min3(dp[j], dp[j-1], leftTop) + 1
if dp[j] > maxSide {
maxSide = dp[j]
}
} else {
// 当前格是零，不能延续上一行的正方形边长。
dp[j] = 0
}
leftTop = top
}
}
return maxSide * maxSide
}
func min3(a, b, c int) int {
if b < a {
a = b
}
if c < a {
a = c
}
return a
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子进行一次常数时间的状态转移。
- 空间复杂度：$O(n)$，
n为列数；只保留一行状态。
关键点总结
[!green]
- 一维数组交替保存上一行和当前行的边长，不能把所有位置都当成同一行。
- 从左向右更新，使左侧状态已经属于本行；上方与左上方则必须读取旧值。
- 当前格为
0时明确覆盖为0，阻断上一行状态继续参与本行扩展。
易错点总结
[!yellow]
- 用相邻状态的最大值扩展，会忽略较短一侧的限制；三块区域都支持才能形成更大的完整正方形。
- 只看上方和左方，会漏掉左上区域中的
0，所以还必须检查左上状态。- 滚动数组遇到
'0'却不清零，会把上一行的边长错误保留到当前格。- 更新
dp[j]后才保存它，下一列读到的左上角就变成当前行新值。- 返回最大边长而不平方，不符合题目要求的面积；访问矩阵时也要注意它存的是字符
'1'，不是数值1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1139. 最大的以 1 为边界的正方形 | 中等 | 原题只要求边框为1，本题整个内部也要为1，不能只查四条边。 |