给定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