LeetCode 1277. 统计全为 1 的正方形子矩阵
题目描述
题意分析
统计矩阵中所有内部元素全部为一的正方形子矩阵。边必须与矩阵行列对齐，单个值为一的格子也算一个正方形，不同位置或不同边长都分别计数，允许重叠。
只要求边框为一并不够，内部也不能含零。返回的是正方形总数，不是最大边长、最大面积，也不是覆盖的不同格子数量。可以按每个正方形唯一的右下角把所有结果分组统计。
解法：右下角动态规划
核心思路
[!blue]
定义
dp[i][j]为以当前格作为右下角的最大全一正方形边长。当前格为零时，任何以它为右下角的正方形都会含零，所以状态是零；当前格为一时，至少能组成边长一的正方形。若要组成边长更大的正方形，上方、左方和左上方相邻格子处都必须能支持相应的小正方形。设这三个最大边长中的最小值为
k，三块边长为k的全一区域与当前这个一合起来，正好覆盖边长k + 1的正方形，因此可以达到这个大小。若再扩大一格，就要求三个邻居都至少支持k + 1，与其中最小值为k矛盾。所以转移恰好是三个邻居最小值加一。如果某个右下角的最大可行边长为
L，那么边长一到L的正方形都存在，且每种边长在这个右下角只有一个，对总数贡献恰好是L。每个正方形又只有一个右下角，把所有格子的状态直接相加就不会重复或遗漏，无需单独枚举所有边长。转移只依赖上一行和当前行左边，可以压缩成一维。处理当前格时，更新前的
dp[j]是上方状态，已经更新的dp[j - 1]是左方状态，变量leftUp保存旧左上状态。先用upper保存将要覆盖的旧dp[j]，完成当前更新后，再令leftUp = upper，交给下一列使用。每行开始将
leftUp置零，并保留额外的第零列为零，统一处理上边界和左边界。遇零格时必须把dp[j]清零，不能让上一行残留状态参与后续转移。
解题步骤
- 创建长度为列数加一的全零滚动数组，累计结果初始为零。
- 每行从左到右处理，行首将
leftUp设为零。- 更新当前格前，先保存旧上方值
upper = dp[j]。- 当前元素为一时，令
dp[j] = min(上方, 左方, 左上方) + 1，并把新边长加入总数；为零时将dp[j]清零。- 令
leftUp = upper，供下一列读取正确的旧左上状态。- 所有格子处理完成后返回累加结果。
代码实现
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[] dp = new int[n + 1];
int res = 0;
for (int i = 1; i <= m; i++) {
int leftUp = 0;
for (int j = 1; j <= n; j++) {
// 保存上一行同列，稍后交给下一列作为旧左上角。
int upper = dp[j];
if (matrix[i - 1][j - 1] == 1) {
dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), leftUp) + 1;
// 最大边长 L 同时贡献一到 L 的全部正方形。
res += dp[j];
} else {
// 零格必须清掉旧行残留状态。
dp[j] = 0;
}
leftUp = upper;
}
}
return res;
}
}
func countSquares(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
dp := make([]int, n+1)
res := 0
for i := 1; i <= m; i++ {
leftUp := 0
for j := 1; j <= n; j++ {
// 保存上一行同列，稍后交给下一列作为旧左上角。
upper := dp[j]
if matrix[i-1][j-1] == 1 {
minVal := dp[j]
if dp[j-1] < minVal {
minVal = dp[j-1]
}
if leftUp < minVal {
minVal = leftUp
}
dp[j] = minVal + 1
// 最大边长 L 同时贡献一到 L 的全部正方形。
res += dp[j]
} else {
// 零格必须清掉旧行残留状态。
dp[j] = 0
}
leftUp = upper
}
}
return res
}
复杂度分析
- 时间复杂度：
O(mn)。每个矩阵格子只处理一次，每次比较三个状态并累加。- 空间复杂度：
O(n)，只保留一行状态及少量变量，输入矩阵不被修改。
关键点总结
[!green]
- 三个邻居最小值限制了可以共同扩张出的正方形，不能只看两个边长。
- 最大边长
L同时代表该右下角有L个正方形，所以求数量时累加状态。- 右下角是唯一归属，允许重叠也不会造成重复计数。
- 一维数组中同时存在新行与旧行状态，旧对角必须在覆盖前单独保存。
易错点总结
[!yellow]
- 取三个来源最大值：只要一个方向缺少支持，就无法扩张，必须由最短的一侧限制。
- 漏掉左上状态：上方和左方的边长不能排除左上内部缺口，三者都需要检查。
- 把状态平方后累加：状态的边长代表可选边长数量，平方得到面积，不是正方形个数。
- 只维护全局最大状态：只能求最大正方形，不能得到所有正方形数量。
- 遇零不清状态：会把上一行的可行边长错误带到当前零格。
- 覆盖后再保存上方或不重置行首对角：下一格会读到错误的旧左上值，破坏滚动转移。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 221. 最大正方形 | 中等 | 局部DP相同，每格状态表示可行最大边长；本题将这些边长累加得到全部正方形数量。 |
| 1139. 最大的以 1 为边界的正方形 | 中等 | 原题只要求边框为1，本题内部也必须为1，不能只检查四条边。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！