我最近对一家公司进行了技术测试，我认为他们在识别二进制矩阵中的形状时遇到了一个非常有趣的问题。
练习的目的是创建一种算法，该算法可以在二进制矩阵中找到最大的X形状，并返回其长度。X是以这种方式定义的：-AX由长度相等的两个对角线组成，它们共享一个唯一的点。例如 ：
101
010
101
包含长度为3的有效X，因此算法将返回3。
1001
0110
0110
1001
不包含任何有效的X，因此算法将返回1，因为1长度的X是单个1。
我设法进行了练习，但是我实现了一个非常凌乱的算法，其时间复杂度估计为O（n3），这很糟糕，不适用于非常大的矩阵。这种复杂性的很大一部分是我用来遍历矩阵的double for循环。
我可以做些什么来制作更简洁的算法？我出于个人兴趣提出问题，并且需要提高我的技能和实践思维。
如果您同意 O(n^2) 额外空间，那么一种选择是构建两个额外数组：一个用于记录以\每个单元格为中心的最长形状的长度，一个用于记录最长 的长度/。（您可以使用三重嵌套循环在 O(n^2) 时间内构建每一个 - 这可能听起来像 O(n^3) 时间，但记忆化意味着您只需要在任何给定\或/，因此最内层的循环可以是摊销常数时间。）然后迭代所有位置；对于任何位置，X以该位置为中心的最大值的大小等于该位置处两个矩阵值中较小的一个。只要跟踪最大的较小的值，就完成了。
最坏情况的时间复杂度为 O(n^2)，这显然是渐近最优的。