java - 列出 16x16x16 矩阵内可能的最大长方体

Question

我有一个 16x16x16 立方矩阵，其中包含[0;k] 可能的值我希望能够列出该矩阵中最大的可能长方体，其中每个值对于该长方体都是相同的。

一个迭代的“扩展”算法可以做到这一点，但鉴于有 4096 个单元，这样做会很昂贵。

有类似的问题，但它们只解决二维矩阵

标签： javaalgorithmmatrix

Answer 1

我希望通过“长方体”，您的意思是它在所有 3 个维度上的大小必须相同。

在这种情况下，具有最大点 (x,y,z) 的最大长方体的大小可以从具有最大点 (x-1,y,z)、(x,y-1, z), (x,y,z-1), (x-1,y-1,z), (x-1,y,z-1), (x,y-1,z-1), 和(x-1, y-1, z-1)。

只需按 sum(x,y,z) 顺序处理这些点，然后，如果所有这些相邻点的值都相同，那么 maximum_cuboid_size(x,y,z) = 1 + min(largest_cuboid_size(..for each neighbor with一个较小的坐标...））

编辑：由于您不需要所有边的长度相同，因此您需要跟踪每个单元格的多个数据才能使用此方法。例如，您可以计算每个（宽度、高度）的最大框尺寸。

您仍然可以从相邻单元格计算每个单元格的条目，但每个单元格最多可以有 256 个条目，因此这是一个较长的过程。

最多需要计算 16^5 (1048576) 个值才能解决整个问题。应该花不到一秒钟的时间，所以也许它对你的目的来说已经足够快了。