在具有 1 和 0 的矩阵中查找全 1 的最大尺寸子矩阵

Question

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

我正在尝试制定动态规划解决方案。但我的递归算法运行时间为 O(n^n)，即使在记忆之后，我也无法想到将其降低到 O(n^4) 以下。有人可以帮助我找到更有效的解决方案吗？

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，其中每个元素代表上面 1 的数量（包括它），直到第一个 0。

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] 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：

  


• • • 弹出堆栈顶部。
• • • 检查是否会创造新的最佳，即(i_cur-i_pop)*h_pop >最好的。

    


  


• • 如果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) Push (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 以达到良好的效果）。

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

现在考虑找到所有元素的最大子数组的问题一维数组中。这可以使用这个简单的算法来解决：

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< /code>，你知道一系列连续的序列在哪里结束。因此，如果您保留当前数量的运行总计（temp 变量），则可以在点击时将该总计与迄今为止的最大值（max 变量）进行比较为零，然后重置运行总计。这将为您提供变量 max 中连续序列的最大长度。

现在您可以使用这个子算法来找到问题的解决方案。首先将 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 之间的矩阵的所有元素：

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

请注意，这类似于一维问题。让我们对各列求和，看看我们得到什么：

1 2 2 2 0 1 0

现在，问题被简化为一维情况，除了我们必须找到连续的 j - i + 1 的子序列（即 <在本例中为 code>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) 算法。除了您所追求的子数组是正方形的情况之外，我还无法弄清楚。然而，有人可能有更好的洞察力，所以再等一下。

Answer 3

定义一个新的矩阵A，A[i,j]中存储两个值：左上角为i,j的最大子矩阵的宽度和高度，从右下角开始填充该矩阵，按行底部到顶部。你会发现四种情况：
当给定矩阵 [i,j]=1 时，执行这些情况

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

情况 2： right 等于当前的但下面的不同，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) 且 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] 时找到的最大值]

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

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;
    }