LeetCode 221. 最大正方形
目录
题目描述
题意分析
给定一个只含字符
'0'和'1'的二维矩阵，找出其中只包含'1'的最大正方形，返回它的面积。有三个信号值得先抓住。其一，题目要的是面积，但正方形由边长唯一确定，面积不好直接比较和递推，所以求解过程中更适合围绕「边长」做文章，最后再平方一次换算成面积。其二，要求的是正方形而不是矩形——正方形只有一个自由度（边长），这比矩形（长和宽两个自由度）的约束强得多，也是本题比「最大矩形」容易的根本原因。其三，矩阵元素是字符
'1'而非数字1，比较时不能写错。数据范围上 $m, n \le 300$，矩阵最多九万个格子，允许对每个格子做常数次甚至线性次的处理。边界情况包括：矩阵全为
'0'时应返回0；单个'1'本身就是边长为 1 的正方形，面积为 1。
解法：一维动态规划
核心思路
暴力枚举正方形会反复检查相同区域。更合适的状态是：
dp[i][j]表示以(i, j)为右下角、且全部为'1'的最大正方形边长。固定右下角后，每个候选正方形都有唯一归属，遍历所有格子即可覆盖全部答案。若当前格是
'1'，它能扩出的边长取决于上方、左方和左上方三个状态：min(上, 左, 左上) + 1。三块区域必须同时完整，任何一处较短都会成为边长上限；若当前格是'0'，状态只能是 0。这个“短板”关系既给出转移，也说明了转移的正确性。二维表只依赖上一行和当前行，可以压缩为一维数组。更新
(i, j)前，dp[j]是“上”，dp[j-1]已更新为“左”，变量leftTop保存尚未覆盖的“左上”。每轮先备份旧dp[j]，再更新状态，最后让它成为下一格的leftTop。
解题步骤
- 建立长度为
n + 1的dp，多出的首位 0 用来统一处理第一列边界。- 逐行扫描；每行开始时令
leftTop = 0。- 处理当前格前先保存
top = dp[j]，避免更新后丢失下一格需要的左上状态。- 当前格为
'1'时，令dp[j] = min(dp[j], dp[j-1], leftTop) + 1并更新最大边长；为'0'时必须重置dp[j] = 0。- 将
leftTop更新为旧值top，继续处理下一列。- 返回最大边长的平方。例如四个相邻
'1'的右下角状态为min(1, 1, 1) + 1 = 2，对应面积 4。
代码实现
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为列数；只保留一行状态。
关键点总结
- 状态保存边长而不是面积，因为边长才能通过邻居的
min + 1直接递推。- “以当前格为右下角”让局部状态与完整答案建立明确对应。
- 一维压缩时必须分清新旧值：
dp[j]是上，dp[j-1]是左，leftTop是左上。- 面试可先写二维 DP 说明状态，再做滚动压缩；二维空间为 $O(mn)$，思路与转移完全相同。
易错点总结
- 返回
maxSide而非maxSide * maxSide：题目要求的是面积。- 当前格为
'0'时不清零：会把上一行的状态错误延续下来。- 更新
dp[j]后才保存旧值：下一列的leftTop会变成当前行数据，状态转移失真。- 漏掉左上状态：矩阵
[[0,1],[1,1]]会被误判存在边长 2 的正方形。- 比较数字
1而不是字符'1'，或忘记dp与原矩阵之间一位下标偏移。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 85. 最大矩形 | 困难 | 放宽为矩形后自由度变多，需按行悬线加单调栈求面积 |
| 1139. 最大的以 1 为边界的正方形 | 中等 | 只要求边框全 1，状态改为向左、向上的连续 1 长度 |
| 1277. 统计全为 1 的正方形子矩阵 | 中等 | 同一转移方程，把维护最大值改成累加所有状态值计数 |
| 1292. 元素和小于等于阈值的正方形的最大边长 | 中等 | 约束从全 1 变为和不超阈值，用二维前缀和代替递推转移 |