1

这是一个面试问题：给定一个布尔矩阵，找出最大的连续方形子矩阵的大小，它只包含“真实”元素。

我在 SO 上找到了这个问题，但不明白答案。所提出的算法将一条对角线从左上移到右下，并随着线的移动跟踪“真实”元素的矩形。

我的问题：

  • 如何跟踪算法中的矩形？
  • 为什么要移动对角线？如果我们移动垂直/水平线或两者都移动怎么办？
  • 如何计算算法复杂度？
4

1 回答 1

4

我无法理解您发布的链接中的答案，而且我不认为那里给出的复杂性最适合您的问题。（它声称有一种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 为了简化，我没有检查数组范围。您可以只考虑超出范围的元素为零。

于 2012-07-30T08:59:32.233 回答