在NxNxN二进制数组中查找仅包含1的最大长方体

Question

给定NxNxN二进制数组(仅包含0或1),我们如何获得具有非平凡解的最大长方体,即在O(N ^ 3)？

-

找到在N×N二进制矩阵中仅包含零但在上部维度中的最大矩形是同样的问题.此外,在我的情况下,最大的矩形可以"穿过阵列的边缘",即空间就像是2D矩阵的圆环.

对于2D数组,如果条目是:

00111
00111
11000
00000
00111

'X'描述的解决方案是

00XXX
00XXX
11000
00000
00XXX

我已经完成了NxN二进制数组的计算,并按照http://tech-queries.blogspot.de/2011/03/maximum-中的想法找到了O(N ^ 2)中最大矩形问题的解决方案.area-rectangle-in-histogram.html.但我不知道如何将它应用于3D阵列.

-

解决方案"越过边缘"的3x3x3阵列示例:

111
100
011

111
001
111

011
110
011

解决方案应该是:

1XX
100
0XX

1XX
001
1XX

0XX
110
0XX

Answer 1

该解决方案具有 O(N ³ log ² N) 复杂度（可以优化为 O(N ³ log N)）。需要额外的大小为 2*8*N ^{3 的}整数数组。

1. 计算 r(i,j,k)：对于 N ²行中的每一行，计算所有非零元素的累积和，当找到零元素时将其重置。
2. 对 K 的各种值执行以下步骤，使用黄金分割搜索（或斐波那契搜索）找到最大结果。
3. 计算 c(i,j,k)：对于 N ²列中的每一列，计算 r(i,j,k) >= K 的所有元素的累积和，当有 r(i,j,k) 的元素时重置它) < K 被发现。有关第 1 步和第 2 步的良好可视化，请参阅此答案。
4. 对 M 的各种值执行最后一步，使用黄金分割搜索找到最大结果。
5. 计算总和：对于第 3 个坐标的 N ^{2 个}值中的每一个，计算 c(i,j,k) >= M 的所有元素的累积总和，当 c(i,j,k) < M 的元素是时重置它成立。计算总和K M 并在必要时更新迄今为止最好的结果。

数组的“跨边”属性以明显的方式处理：迭代每个索引两次并保持所有累积和不大于 N。

对于多维情况，该算法具有 O(N ^D log ^D-1 N) 时间复杂度和 O(D*N ^D ) 空间复杂度。

优化为 O(N ³ log N)

算法的步骤 4 为 M 设置一个全局值。如果 M 的值是本地确定的，则可以排除此步骤（并且复杂性降低log N）。

为此，应改进步骤 5。它应该维护一个双端队列（其头部包含 M 的本地值）和一个堆栈（保留所有 M 值的起始位置，从队列中逐出）。

当 c(i,j,k) 增加时，它被附加到队列的尾部。

如果 c(i,j,k) 减小，所有较大的值都会从队列的尾部移除。如果它进一步减少（队列为空），则堆栈用于恢复“sum”值并将相应的“M”值放入队列。

如果这允许增加本地解决方案的价值，那么可以从队列的头部删除几个元素（并推送到堆栈）。

对于多维情况，这种优化给出了 O(N ^D log ^D-2 N) 复杂度。

Answer 2

这里只有 O(N^4)。

假设您将 cubiod 存储在 bool cuboid[N][N][N] 中；

bool array2d[N][N];

for(int x_min = 0; x_min < N; x_min++) {
   //initializing array2d
   for(int y = 0; y < N; y++) {
      for(int z = 0; z < N; z++) {
         array2d[y][z] = true;
      }
   }

   //computation
   for(int x_max = x_min; x_max < N; x_max++) {
      // now we want to find largest cube that
      // X coordinates are equal to x_min and x_max

      // cells at y,z can be used in cube if and only if
      // there are only 1's in cuboid[x][y][z] where x_min <= x <= x_max

      // so lets compute for each cell in array2d,
      // if are only 1's in cuboid[x][y][z] where x_min <= x <= x_max
      for(int y = 0; y < N; y++) {
         for(int z = 0; z < N; z++) {
            array2d[y][z] &= cubiod[x_max][y][z];
         }
      }

      //you already know how to find largest rectangle in 2d in O(N^2)
      local_volume = (x_max - x_min + 1) * find_largest_area(array2d);

      largest_volume = max(largest_volumne, local_volume);
   }
}

您可以使用相同的技巧来计算 X 维度的最佳解决方案。只需将问题减少到 X-1 维度即可。复杂度：O(N^(2*X-2))。