这是一个面试问题:给定一个布尔矩阵,找出最大的连续方形子矩阵的大小,它只包含“真实”元素。
我在 SO 上找到了这个问题,但不明白答案。所提出的算法将一条对角线从左上移到右下,并随着线的移动跟踪“真实”元素的矩形。
我的问题:
- 如何跟踪算法中的矩形?
- 为什么要移动对角线?如果我们移动垂直/水平线或两者都移动怎么办?
- 如何计算算法复杂度?
这是一个面试问题:给定一个布尔矩阵,找出最大的连续方形子矩阵的大小,它只包含“真实”元素。
我在 SO 上找到了这个问题,但不明白答案。所提出的算法将一条对角线从左上移到右下,并随着线的移动跟踪“真实”元素的矩形。
我的问题:
我无法理解您发布的链接中的答案,而且我不认为那里给出的复杂性最适合您的问题。(它声称有一种O(N^(3/2)*logN)
算法,其中N=n*n
是原始矩阵中的元素数。)
对于您最大的平方子矩阵问题,有一个 DP 算法,其复杂性与元素的数量成线性关系:
设原始矩阵为A[n][n]
,我们试图找到一个矩阵B[n][n]
,其中B[i][j]
表示其右下元素为 的最大方形子矩阵的大小A[i][j]
。所以
for (i = 0 ; i < n ; ++i)
for (j = 0 ; j < n ; ++j)
if (A[i][j] == 0) B[i][j] = 0;
else {
if (B[i-1][j] != B[i][j-1]) {
B[i][j] = min(B[i-1][j], B[i][j-1]) + 1
} else {
if (A[i-B[i-1][j]][j-B[i-1][j]] == 1)
B[i][j] = B[i-1][j] + 1;
else
B[i][j] = B[i-1][j];
}
}
最大的 B[i][j] 就是答案。
ps 为了简化,我没有检查数组范围。您可以只考虑超出范围的元素为零。