在一个由1和0组成的矩阵中，查找所有只包含1的子矩阵中最大的那个子矩阵。

Question

假设您有一个mXn位图，由数组M [1..m，1..n]表示，其条目均为0或1。全一块是形式为M [i..i0，j..j0]的子数组，其中每个位都等于1。请描述并分析一种有效的算法，以查找具有最大面积的M中的全一块。

我正在尝试制作动态规划解决方案。但是我的递归算法运行时间为O（n ^ n），即使进行了记忆化，我也无法将其降低到O（n ^ 4）以下。有人能帮我找到更有效的解决方案吗？

- john

---

你是如何创造出O(n^n)算法的？即使是直接的解决方案（检查所有n^4个矩形并验证每个矩形）都需要O(n^6)的时间。 - Nikita Rybak

Answer 1

一个O(N)（元素数量）的解决方案：

A
1 1 0 0 1 0
0 1 1 1 1 1
1 1 1 1 1 0
0 0 1 1 0 0 

生成一个数组C，其中每个元素表示从它开始到第一个0之间有多少个1。

C
1 1 0 0 1 0
0 2 1 1 2 1
1 3 2 2 3 0
0 0 3 3 0 0 

我们想要找到行 R，以及左右索引 l，r，使得 (r-l+1)*min(C[R][l..r]) 最大。这里是一个算法，可以在 O(cols) 时间内检查每一行：

维护一个由对 (h, i) 组成的栈，其中 C[R][i-1] < h ≤ C[R][i]。 在任何位置 cur，对于堆栈上的所有对 (h, i)，我们应该有 h=min(C[R][i..cur])。

对于每个元素：

• 如果 h_cur>h_top
• • 压入 (h, i)。
• 否则：
• • 当 h_cur<h_top 时：
• • • 弹出堆栈顶部。
• • • 检查是否会产生新的最佳解，即 (i_cur-i_pop)*h_pop > best。
• • 如果 h_cur>h_top
• • • 压入 (h, i_lastpopped)。

以下是在我们的示例中为第三行执行此操作的示例：

  i =0      1      2      3      4      5
C[i]=1      3      2      2      3      0
                                 (3, 4)
 S=         (3, 1) (2, 1) (2, 1) (2, 1)
     (1, 0) (1, 0) (1, 0) (1, 0) (1, 0)    
     (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) 

i=0, C[i]=1) 压入 (1, 0)。
i=1, C[i]=3) 压入 (3, 1)。
i=2, C[i]=2) 弹出 (3, 1)。检查是否有新的最佳值(2-1)*3=3。
        最后一个弹出的i是1，因此压入 (2, 1)。
i=3, C[i]=2) h_cur=h_top，所以什么也不做。
i=4, C[i]=3) 压入 (3, 4)。
i=5, C[i]=0) 弹出 (3, 4)。检查是否有新的最佳值(5-4)*3=3。
        弹出 (2, 1)。检查是否有新的最佳值(5-1)*2=8。
        弹出 (1, 0)。检查是否有新的最佳值(5-0)*1=5。
        结束。（好吧，我们可能应该在最后加上额外的项 C[cols]=0 以确保正确）。

- Nabb

---

+1. 我没能完全理解你的推断（特别是h是什么），但现在我明白了，对于每一行来说，你实际上是调用了一个线性时间算法来查找该行底部直方图下最大矩形。那个“子程序”似乎与这里的算法#4相匹配：http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx - j_random_hacker

实际上，复杂度是O(n^2)。你必须至少处理每一行或每一列一次。 - brainfood

Answer 2

这里有一个 O(numCols*numLines^2) 的算法。令 S[i][j] = 列 j 的前 i 个元素的和。

我将在这个例子上演示这个算法：

M
1 1 0 0 1 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 1 1 0 0 

我们有：

S
1 1 0 0 1 0
1 2 1 1 1 1
2 3 2 2 1 1 
2 3 3 3 1 1

现在考虑在一维数组中查找所有1的最大子数组的问题。可以使用以下简单算法解决：

append 0 to the end of your array
max = 0, temp = 0
for i = 1 to array.size do
  if array[i] = 1 then
    ++temp
  else
    if temp > max then
      max = temp
    temp = 0

举个例子，如果你有这个一维数组：

1 2 3 4 5 6
1 1 0 1 1 1

你需要这样做：

首先添加一个0：

1 2 3 4 5 6 7
1 1 0 1 1 1 0

现在，注意到每当你遇到一个0时，就知道连续的1序列结束的位置。因此，如果你保持当前1的数量的运行总数（temp变量），当你遇到0时，可以将该总数与到目前为止的最大值（max变量）进行比较，然后重置运行总数。这将给出变量max中连续1序列的最大长度。

现在，您可以使用此子算法来查找问题的解决方案。首先向矩阵附加一个0列，然后计算S。

然后：

max = 0
for i = 1 to M.numLines do
  for j = i to M.numLines do
    temp = 0
    for k = 1 to M.numCols do
      if S[j][k] - S[i-1][k] = j - i + 1 then
        temp += j - i + 1
      else
        if temp > max then
          max = temp
        temp = 0

基本上，对于每个可能的子数组高度（有O(numLines^2)个可能的高度），你可以通过将一维数组算法（O(numCols)）应用到该高度上，找到具有最大面积的那个。

考虑以下“图片”：

   M
   1 1 0 0 1 0 0
i  0 1 1 1 0 1 0
j  1 1 1 1 0 0 0
   0 0 1 1 0 0 0

这意味着我们的高度为j - i + 1。现在，取出矩阵中介于i和j之间（包括i和j）的所有元素:

0 1 1 1 0 1 0
1 1 1 1 0 0 0

注意这类似于一维问题。我们将列相加并查看结果：

1 2 2 2 0 1 0

现在，问题被简化为一维情况，唯一的例外是我们必须找到一个连续的子序列，其长度为j-i+1（在本例中为2）。这意味着我们j-i+1个“窗口”中的每一列必须都是由1组成的。我们可以通过使用S矩阵来有效地检查这一点。

要理解S的工作原理，请再次考虑一维情况：令s[i] = a向量的前i个元素之和。那么子序列a[i..j]的总和是多少？它是从第一个元素到包括a[j]的所有元素的总和，减去从第一个元素到包括a[i-1]的所有元素的总和，即s[j]-s[i-1]。二维情况也是如此，只是对于每一列我们有一个s。

希望这很清楚，如果您有更多问题，请提出。我不知道这是否符合您的需求，但我认为还有一种基于动态规划的O(numLines*numCols)算法，但我还没有完全弄清楚，除非您寻找的子数组是正方形。不过，也许有人可以提供更好的见解，所以请稍等一会。

- IVlad

---

+1个好的解决方案（我认为在一般情况下无法实现O(n*m)复杂度，这可能是最好的解决方案）。顺便说一句，在你的例子中，_S_的左下角值似乎是错误的。此外，如果您能更清楚地解释主要思想（尽管用语言很难，但思想更具“视觉效果”），我认为您可能会获得更多的赞同。 - Nikita Rybak

@Nikita Rybak - 感谢您的建议，我已经纠正了 S 中的错误，并尝试更好地解释了这个想法。 - IVlad

有人告诉我这个问题也可以用O(n^2logn)的时间复杂度解决。有人支持O(n^2logn)吗？ - Akhil

Answer 3

定义一个新的矩阵A，它将在A[i,j]中存储两个值：左上角位于i,j的最大子矩阵的宽度和高度。从右下角开始，按行从底部到顶部填充此矩阵。当给定矩阵在[i,j]=1时，执行以下四种情况：

情况1：原始矩阵中的右侧或底部相邻元素都不等于当前元素，即 M[i,j] != M[i+1,j] and M[i,j] != M[i,j+1]，其中 M 是原始矩阵，在这种情况下，A[i,j] 的值为 1x1。

情况2：右侧的相邻元素与当前元素相等，但底部的元素不同，A[i,j].width 的值为 A[i+1,j].width+1，A[i,j].height 的值为 1。

情况3：底部的相邻元素相等，但右侧的元素不同，A[i,j].width 的值为 1，A[i,j].height 的值为 A[i,j+1].height+1。

情况4：两个相邻元素都相等： 三个矩形被考虑：

1. A[i,j].width=A[i,j+1].width+1; A[i,j].height=1;

2. A[i,j].height=A[i+1,j].height+1; a[i,j].width=1;

3. A[i,j].width = min(A[i+1,j].width+1,A[i,j+1].width) and A[i,j].height = min(A[i,j+1]+1,A[i+1,j])

在上述三种情况中，面积最大的那个将被视为代表此位置的矩形。

具有左上角在i,j处的最大矩阵大小为A[i,j].width*A[i,j].height，因此您可以在计算A[i,j]时更新找到的最大值。

底行和最右列元素被视为其底部和右侧分别不同的邻居。

- Tanu Saxena

Answer 4

这是一个C#中O(N)的实现。

思路是使用动态规划来构建一个累积矩阵，该矩阵的大小包括当前单元格本身的最大子矩阵。

    public static int LargestSquareMatrixOfOne(int[,] original_mat)
    {
        int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)];
        AccumulatedMatrix[0, 0] = original_mat[0, 0];
        int biggestSize = 1;
        for (int i = 0; i < original_mat.GetLength(0); i++)
        {
            for (int j = 0; j < original_mat.GetLength(1); j++)
            {
                if (i > 0 && j > 0)
                {
                    if (original_mat[i, j] == 1)
                    {
                        AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1;
                        if (AccumulatedMatrix[i, j] > biggestSize)
                        {
                            biggestSize = AccumulatedMatrix[i, j];
                        }
                    }
                    else
                    {
                        AccumulatedMatrix[i, j] = 0;
                    }
                }
                else if ( (i > 0 && j == 0) || (j > 0 && i == 0))
                {
                    if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; }
                    else { AccumulatedMatrix[i, j] = 0; }
                }
            }
        }
        return biggestSize;
    }

- aerin

---

请注意，问题并没有明确指定矩阵必须是方阵！ - undefined