algorithm - 找到最大的相交对角线

Question

这是一道面试题：

给定一个 m 位矩阵，找到矩阵中形成的最大 X，并返回该 X 对角线的大小。X 定义为 2 个大小相同的对角线，它们共享一个 1。

例如，矩阵：

00100001
00010010
00001100
00001100
00010010
00100001

将返回大小为 1，因为给定的 X 无效，因为中间部分不共享单个 1。另一方面，以下矩阵

101
010
101

将返回值 3，因为对角线是 3。编写这样的程序。

我理解这里讨论的第一个解决方案，但我想知道是否有更有效的方法来解决这个问题。想法？

Answer 1

关于时间复杂度，没有渐近更好的解决方案。一个较弱的问题是检查矩阵是否包含任何 1 单元格。对于这个问题，您显然必须访问每个单元格，这会给您 O(nxm)。现在这是原始问题的下限，也有 O(nxm)。Qed。