algorithm - 在二进制矩阵中找到最大的 X 形状

Question

我最近对一家公司进行了一次技术测试，我认为他们遇到了一个关于识别二进制矩阵中的形状的非常有趣的问题。

该练习的目标是创建一种算法，该算法可以在二进制矩阵中找到最大的 X 形状，并返回其长度。 X 以这种方式定义:-A X 由两条等长的对角线组成，它们共享一个唯一点。例如:

101
010
101

包含长度为 3 的有效 X，因此算法将返回 3。

1001
0110
0110
1001

不包含任何有效的 X，因此算法将返回 1，因为长度为 1 的 X 是单个 1。

我设法做了这个练习，但我实现了一个非常困惑的算法，时间复杂度估计为 O(n3)，这很糟糕，不适合非常大的矩阵。这种复杂性的很大一部分是我用来遍历矩阵的双 for 循环。

我可以做些什么来制作更清晰的算法？我问这个问题是出于个人兴趣，需要提高我的技能和实践思维。

Answer 1

如果您可以接受 O(n^2) 的额外空间，那么一种选择是构建两个额外的数组:一个用于记录以每个单元格为中心的最长 \ 形状的长度，一个记录最长的/的长度。 (您可以使用三重嵌套循环在 O(n^2) 时间内构建每一个——这听起来像是 O(n^3) 时间，但内存意味着您只需要迭代一次 在任何给定的 \ 或 / 上，因此最内层的循环可以是摊销常数时间。)然后迭代所有位置；对于任何位置，以该位置为中心的最大 X 的大小等于该位置两个矩阵值中较小的一个。只需跟踪最大的较小值，您就完成了。

最坏情况下的时间复杂度为 O(n^2)，这显然是渐近最优的。