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

Question

这是一道面试题:

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

例如矩阵:

00100001
00010010
00001100
00001100
00010010
00100001

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

101
010
101

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

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

Answer 1

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