🤖 AI总结
主题
力扣4016题：在矩阵中找两个互不重叠且全为1的k×k正方形，求最大面积。
摘要
给定01矩阵，找两个不重叠全1的k×k正方形，通过上下/左右分割及DP求最大面积。
关键信息
- 1 利用上下或左右分割线枚举不重叠正方形。
- 2 通过转置矩阵处理左右分割情况。
- 3 使用最大正方形DP和提前退出优化，时间复杂度O(mn)。
2026-11-05：两个不重叠子正方形的最大面积。用go语言，给定一个 m 行 n 列的整数矩阵。矩阵中的 1 表示该位置可以使用，0 表示该位置不能使用。
现在需要从矩阵中选出两个大小为 k × k 的正方形区域，并满足：
1. 每个正方形区域覆盖的所有格子都必须是 1；
2. 两个正方形区域不能覆盖任何一个相同的格子，也就是它们不能重叠；
3. 两个正方形的边长都必须是 k。
如果能够找到符合条件的两个正方形，则返回其中一个正方形的面积，即 k × k；如果找不到这样的两个正方形，则返回 0。
用纯文本理解就是：在矩阵中找两个互不重叠、且内部全部由 1 组成的 k 乘 k 方块；能找到就输出 k 乘 k，找不到就输出 0。
mat.length == m。
mat[i].length == n。
1 <= m, n <= 500。
mat[i][j] 是 0 或 1。
输入： mat = [[1,1,1,0],[1,1,1,1],[0,0,1,1]]。
输出： 4。
解释：
最大且相等的无重叠正方形的边长为 k = 2，面积为 4。
第一个正方形从左上角 (0, 0) 开始，覆盖单元格 (0, 0)、(0, 1)、(1, 0) 和 (1, 1)。
第二个正方形从左上角 (1, 2) 开始，覆盖单元格 (1, 2)、(1, 3)、(2, 2) 和 (2, 3)。
因此，答案是 4。
题目来自力扣4016。
大体过程如下：
1. 先理解“两个不重叠正方形”的分割性质。
两个轴对齐的正方形如果不重叠，那么它们的行区间一定不相交，或者列区间一定不相交。也就是说，要么存在一条水平分割线，使一个正方形完全在上半部分、另一个完全在下半部分；要么存在一条垂直分割线，使一个在左半部分、另一个在右半部分。
代码中的 calc 只处理“上下分割”的情况；把矩阵转置后，原来的“左右分割”就变成了“上下分割”，所以 maxArea 分别计算原矩阵和转置矩阵，最后取较大值。
2. maxArea 的总入口。
先对原矩阵调用 calc，得到两个正方形一上一下时的最大面积；再对转置矩阵调用 calc，得到两个正方形一左一右时的最大面积；两者取较大值返回。
因为任意两个不重叠正方形必然属于上下分离或左右分离之一，所以这样不会漏掉最优情况。
3. calc 先计算“下半部分”的后缀最大正方形边长。
对当前矩阵，设行数为 m、列数为 n。准备一个 sufMax 数组，用来记录从某一行到底部的子矩阵中，最大的全 1 正方形边长。
然后使用最大正方形 DP 的空间优化写法：只保留一维滚动数组 f，长度约为 n+1，表示当前扫描行中各个位置能形成的最大全 1 正方形边长。
计算 sufMax 时从最后一行向上扫描到第 1 行，不处理第 0 行。每处理完一行 i，就维护一个 mx，表示从第 i 行到底部已经扫描过的区域中，最大全 1 正方形边长，并记录 sufMax[i] = mx。
这样 sufMax[i] 的含义就是：第 i 行到最后一行的子矩阵中，最大全 1 正方形的边长。后续如果水平分割线在第 i 行和第 i+1 行之间，那么下半部分从 i+1 行开始，最大边长就是 sufMax[i+1]。
这里跳过第 0 行，是因为水平分割线下方至少从第 1 行开始，而 sufMax[1] 到 sufMax[m-1] 已经足够覆盖所有上下分割情况。
4. DP 更新的核心含义。
处理某个格子时，如果它是 0，则以它为边角形成的全 1 正方形不存在，对应 DP 值清零。
如果它是 1，则它能形成的最大正方形边长，等于三个相邻已计算方向的最小 DP 值加一。
从下往上扫描时，这三个方向可以理解为下方、左方、左下方；从上往下扫描时，则是上方、左方、左上方。虽然扫描方向不同，但最大全 1 正方形边长的统计是正确的。
一维数组中，last 用来保存上一行前一列的旧 DP 值，供当前格子的斜方向依赖使用；每处理一列后，把旧的上方或下方同列值保存下来，供下一列作为斜方向值使用。这样只需要一行大小的 DP 数组，不需要完整二维 DP 表。
5. calc 再扫描“上半部分”并枚举水平分割线。
重置滚动 DP 数组，令 preMax = 0，表示上半部分当前已经扫描的行中，最大全 1 正方形边长。
然后从第 0 行开始向下扫描到第 m-2 行。每扫描一行，就用同样的最大正方形 DP 更新当前行状态，并更新 preMax，使它表示第 0 行到当前第 i 行的上半部分中，最大全 1 正方形边长。
当第 i 行处理完后，就相当于枚举了一条水平分割线：上半部分是第 0 行到第 i 行，下半部分是第 i+1 行到最后一行。
上半部分最大边长为 preMax，下半部分最大边长为 sufMax[i+1]。题目要求两个正方形边长相等，因此能同时取到的最大相等边长是二者较小值，即候选 k = min(preMax, sufMax[i+1])。候选面积就是 k*k。
如果候选边长大于当前记录的最优边长 ans，就更新 ans。
注意：如果某一部分存在边长为 a 的全 1 正方形，而候选 k 不大于 a，那么一定可以在这个大正方形中取出一个 k×k 的全 1 子正方形，所以取 min 得到的候选 k 是可行的。
6. 提前退出优化。
在枚举水平分割线时，如果当前下半部分的最大可能边长 sufMax[i+1] 已经不大于当前最优边长 ans，那么候选 k = min(preMax, sufMax[i+1]) 一定不会超过 ans。
又因为继续向下枚举时，下半部分的范围只会变小，sufMax 不会增大，所以后续也不可能得到更优答案，可以直接结束 calc 的枚举循环。
7. calc 返回面积。
calc 内部维护的 ans 是最大可行边长 k，最后返回 ans*ans，即面积。如果找不到两个符合条件的正方形，ans 保持 0，最终返回 0。
8. 转置矩阵处理另一方向。
transpose 创建一个 n 行 m 列的新矩阵，新矩阵第 i 行第 j 列等于原矩阵第 j 行第 i 列。
原矩阵中“左右分开”的两个正方形，在转置矩阵中就变成“上下分开”。因此对转置矩阵再调用一次 calc，就等价于枚举原矩阵的垂直分割线，处理两个正方形一左一右的情况。
9. 示例结果。
在给定矩阵中，可以找到两个 2×2 的全 1 正方形，它们分别位于左上和右下附近，并且在列方向上是分开的。原矩阵直接 calc 主要处理上下分割，可能不能直接得到最优；转置后，左右分割变成上下分割，calc 找到 k=2，返回面积 4。maxArea 取两个方向的最大值，因此输出 4。
总的时间复杂度：
• 转置矩阵需要遍历 m×n 个元素，时间 O(mn)。
• calc(mat) 需要扫描矩阵并做常数时间 DP 更新，时间 O(mn)。
• calc(transpose(mat)) 处理的是 n×m 矩阵，时间 O(nm)。
• 因此总时间复杂度为 O(mn)。
总的额外空间复杂度：
• 单次 calc 中，sufMax 长度为 m，滚动 DP 数组长度约为 n，额外空间为 O(m+n)。
• 转置矩阵需要创建一个 n×m 的新矩阵，额外空间为 O(mn)。
• 因此按代码整体计算，总额外空间复杂度为 O(mn + m + n)，即 O(mn)。
• 如果不把转置矩阵算入，只看 calc 的核心算法，则额外空间是 O(m+n)。
Go完整代码如下：
package main
import (
"fmt"
)
func maxArea(mat [][]int)int {
a := calc(mat)
b := calc(transpose(mat))
if a > b {
return a
}
return b
}
func calc(mat [][]int)int {
m := len(mat)
n := len(mat[0])
// 221. 最大正方形（空间优化写法）
// 计算 mat 下半部分的最大正方形的边长
sufMax := make([]int, m)
f := make([]int, n+1)
mx := 0
for i := m - 1; i > 0; i-- {
last := 0
for j := 0; j < n; j++ {
if mat[i][j] == 1 {
tmp := f[j+1]
f[j+1] = minInt(minInt(last, f[j+1]), f[j]) + 1
last = tmp
if f[j+1] > mx {
mx = f[j+1]
}
} else {
f[j+1] = 0
last = 0
}
}
sufMax[i] = mx
}
ans := 0
// 计算 mat 上半部分的最大正方形的边长
preMax := 0
for i := range f {
f[i] = 0
}
for i := 0; i < m-1; i++ {
last := 0
for j := 0; j < n; j++ {
if mat[i][j] == 1 {
tmp := f[j+1]
f[j+1] = minInt(minInt(last, f[j+1]), f[j]) + 1
last = tmp
if f[j+1] > preMax {
preMax = f[j+1]
}
} else {
f[j+1] = 0
last = 0
}
}
if sufMax[i+1] <= ans {
break// 最优性优化：继续循环不会让 ans 变大
}
// 题目要求两个正方形的边长相等，所以取 min
if v := minInt(preMax, sufMax[i+1]); v > ans {
ans = v
}
}
return ans * ans
}
// 转置矩阵 mat
func transpose(mat [][]int) [][]int {
m := len(mat)
n := len(mat[0])
a := make([][]int, n)
for i := 0; i < n; i++ {
a[i] = make([]int, m)
for j := 0; j < m; j++ {
a[i][j] = mat[j][i]
}
}
return a
}
func minInt(a, b int)int {
if a < b {
return a
}
return b
}func main() {
mat := [][]int{{1, 1, 1, 0}, {1, 1, 1, 1}, {0, 0, 1, 1}}
result := maxArea(mat)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def max_area(mat):
a = calc(mat)
b = calc(transpose(mat))
return a if a > b else b
def calc(mat):
m = len(mat)
n = len(mat[0])
# 221. 最大正方形（空间优化写法）
# 计算 mat 下半部分的最大正方形的边长
suf_max = [0] * m
f = [0] * (n + 1)
mx = 0
for i in range(m - 1, 0, -1):
last = 0
row = mat[i]
for j in range(n):
if row[j] == 1:
tmp = f[j + 1]
f[j + 1] = min(last, f[j + 1], f[j]) + 1
last = tmp
if f[j + 1] > mx:
mx = f[j + 1]
else:
f[j + 1] = 0
last = 0
suf_max[i] = mx
ans = 0
# 计算 mat 上半部分的最大正方形的边长
pre_max = 0
for i in range(n + 1):
f[i] = 0
for i in range(m - 1):
last = 0
row = mat[i]
for j in range(n):
if row[j] == 1:
tmp = f[j + 1]
f[j + 1] = min(last, f[j + 1], f[j]) + 1
last = tmp
if f[j + 1] > pre_max:
pre_max = f[j + 1]
else:
f[j + 1] = 0
last = 0
if suf_max[i + 1] <= ans:
break # 最优性优化：继续循环不会让 ans 变大
# 题目要求两个正方形的边长相等，所以取 min
v = min(pre_max, suf_max[i + 1])
if v > ans:
ans = v
return ans * ans
# 转置矩阵 mat
def transpose(mat):
m = len(mat)
n = len(mat[0])
a = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
a[i][j] = mat[j][i]
return aif __name__ == "__main__":
mat = [[1, 1, 1, 0], [1, 1, 1, 1], [0, 0, 1, 1]]
result = max_area(mat)
print(result)
C++完整代码如下：
using namespace std;int maxArea(const vector int >>& mat);
int calc( const vector int >>& mat) {
int m = mat.size();
int n = mat[ 0 ].size();
// 221. 最大正方形（空间优化写法）
// 计算 mat 下半部分的最大正方形的边长
vector< int > sufMax(m, 0 );
vector< int > f(n + 1 , 0 );
int mx = 0 ;
for ( int i = m - 1 ; i > 0 ; i--) {
int last = 0 ;
for ( int j = 0 ; j < n; j++) {
if (mat[i][j] == 1 ) {
int tmp = f[j + 1 ];
f[j + 1 ] = min({last, f[j + 1 ], f[j]}) + 1 ;
last = tmp;
if (f[j + 1 ] > mx) {
mx = f[j + 1 ];
}
} else {
f[j + 1 ] = 0 ;
last = 0 ;
}
}
sufMax[i] = mx;
}
int ans = 0 ;
// 计算 mat 上半部分的最大正方形的边长
int preMax = 0 ;
fill(f.begin(), f.end(), 0 );
for ( int i = 0 ; i < m - 1 ; i++) {
int last = 0 ;
for ( int j = 0 ; j < n; j++) {
if (mat[i][j] == 1 ) {
int tmp = f[j + 1 ];
f[j + 1 ] = min({last, f[j + 1 ], f[j]}) + 1 ;
last = tmp;
if (f[j + 1 ] > preMax) {
preMax = f[j + 1 ];
}
} else {
f[j + 1 ] = 0 ;
last = 0 ;
}
}
if (sufMax[i + 1 ] <= ans) {
break ; // 最优性优化：继续循环不会让 ans 变大
}
// 题目要求两个正方形的边长相等，所以取 min
int v = min(preMax, sufMax[i + 1 ]);
if (v > ans) {
ans = v;
}
}
return ans * ans;
}
// 转置矩阵 mat
vector int >> transpose( const vector int >>& mat) {
int m = mat.size();
int n = mat[ 0 ].size();
vector int >> a(n, vector< int >(m));
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m; j++) {
a[i][j] = mat[j][i];
}
}
return a;
}
int maxArea( const vector int >>& mat) {
int a = calc(mat);
vector int >> t = transpose(mat);
int b = calc(t);
return a > b ? a : b;
}
int main() {
vector int >> mat = {
{ 1 , 1 , 1 , 0 },
{ 1 , 1 , 1 , 1 },
{ 0 , 0 , 1 , 1 }
};
int result = maxArea(mat);
cout << result << endl;
return 0 ;
}
芯谷ai：https://xinguhub.com/sign-up?aff=txk5
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
