我有一个 3D 数组。在这个数组中，我想找到可以组合成更大元素的元素。矩形不能相互重叠。最好我想先找到最大的矩形，但先到先得也不会错，特别是如果这样可以提高性能。
例如
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
1 1 0 0 1
将产生（因为 3x3 是可以找到的最大矩形；位置 1, 0 到 3, 2 - zerobased）：
0 0 0
0 0 0
0 0 0
和（因为 1x2 是可以找到的下一个最大矩形；位置 0, 1 到 0, 2）：
0
0
和（因为 2x1 是可以找到的下一个最大矩形；位置 2, 3 到 3, 3）：
0 0
当然（左边是位置 4, 1；不是更大但仍需要使用）
0
作为更大的元素（我只需要知道零或一）。目的是减少体素网格的对撞机数量。
我不知道这种算法的名称，也许我可以找到自己如何做到这一点。
如果有人可以为此提供一些可行的信息，那就太好了！
对于 2D 情况，用于查找最大矩形的算法是“直方图下的最大矩形区域”。这是一个非常简单的 O(n) 算法，这里也进行了讨论。
诀窍是可视化您的矩阵实际上可能被处理为n长度直方图m- 在每一行，从上到下，您要么有一列高度0（在您的示例中将由数字 1 表示），要么有一列height[i-1][j] + 1当前字符为 a 时的高度0。因此，每一行都被处理，O(m)总复杂度变为O(n*m)。现在，既然你想要所有的矩形，而不仅仅是最大的，你只需调整算法以“消耗”任何你满意的矩形，也就是说，每当你找到一个流浪的时候1中断你的矩形形成，你可以“消耗”上面将被中断的矩形，并确保它下面的其他位置将在高度 0 或 1 处重新开始，有效地设置height[i-1][jbegin~jend] = 0. （在哪里jbegin和jend是在 line 结束的矩形的开始和结束，i-1您刚刚选择“使用”，因为它在 line 处被阻塞i）
对于 3D 情况，您必须了解直方图算法的工作原理，以便您可以开发您的适应，但它基本上应该成为上述更复杂的版本，跟踪额外的坐标。这可能不是最容易实现的方法，但如果这是您需要的，它将产生最佳性能。