最有效的算法是在二维图中找到最大的正方形

以下是如何在最佳时间量 O(nm)内完成此操作.这是建立在@dukeling的洞察力之上,您永远不需要检查尺寸小于当前已知最佳解决方案的解决方案.

关键是能够构建一个可以在O(1)时间内回答此查询的数据结构.

广场的左上角是r,c并且大小为k,是否存在障碍？

为了解决这个问题,我们将支持回答一个稍微更难的问题,也在O(1)中.

从r1,c1到r2,c2的矩形中的项目数是多少？

通过矩形计数问题的答案很容易回答方形存在问题.

要回答矩形计数问题,请注意,如果您已经预先计算了左上角开始的每个矩形的答案,那么您可以通过一种聪明/包含来回答从r1,c1到r2,c2的一般问题仅使用从左上角开始的矩形的排除策略

              c1   c2  
-----------------------
|             |    |  |
|   A         | B  |  |
|_____________|____|  |  r1
|             |    |  |
|    C        |  D |  |
|_____________|____|  |  r2
|_____________________|

我们想要D里面的东西数量.从左上角我们预先计算的数量.

Count(D) = Count(A ? B ? C ? D) - Count(A ? C) - Count(A ? B) + Count(A)

你可以通过做一些聪明的行/列部分和来预先计算O(nm)中的所有左上角矩形,但我会把它留给你.

然后回答您想要解决的问题,只需检查可能的解决方案,从至少与您最熟悉的解决方案一样的解决方案开始.你知道的最佳状态只会在最小(n,m)次总数上变得更好,所以best_possible增量很少发生,并且几乎所有的正方形都会在O(1)时间内被拒绝.

best_possible = 0
for r in range(n):
 for c in range(m):
   while True:                      
     # this looks O(min(n, m)), but it's amortized O(1) since best_possible
     # rarely increased.      
     if possible(r, c, best_possible+1):
       best_possible += 1
     else:
       break

一个想法,利用二进制搜索.

基本理念:

从左上角开始.看看1x1平方是否有效.

如果它可以工作,将方块的边长增加1并重复.

如果它不起作用,请向右移动并重复.如果您已到达最右侧位置,请移至下一行.

原生方法:

我们可以简单地检查每个步骤中每个方块的每个可能的单元格,但这是相当低效的.

优化方法:

当增加平方大小时,我们可以在下一行和列上进行二进制搜索,以查看该行/列是否在任何这些位置包含障碍物.

当向右移动时,我们可以对每个下一列进行二进制搜索,以确定该列是否包含任何这些位置的障碍物.

向下移动时,我们可以在目标位置的每个列上执行类似的二进制.

实施说明:

首先,我们需要遍历所有的行和列,并设置包含每个行的障碍位置的数组,我们可以将其用于二进制搜索.

运行时间:

我们进行2次二进制搜索以增加平方大小,并且平方大小最大化网格的大小,因此它相当小(O(min(m,n) log max(m,n)))并且由下面的主导.

除此之外,对于每个位置,我们对列进行单个二进制搜索.

因此,对于具有m列和n行的网格,总体复杂性是O(mn log m).

但请注意,当网格稀疏时,我们实际上在下面搜索的数量很少.

例:

对于你的例子:

 012345678901234567890123456
0...........................
1....o......................
2............o..............
3...........................
4....o......................
5...............o...........
6...........................
7......o..............o.....
8..o.......o................

我们首先在左上角尝试一个1x1的方块,这样可行.

然后2x2平方.为此,我们[0,1]对行1上的范围进行二分搜索,其可以简单地表示{4}- 对应于障碍物所在位置的单个位置的数组.我们还[0,1]对第1列的范围进行二分搜索,该范围不包含任何障碍,因此是一个空数组 - {}.

然后一个3x3平方.为此,我们[0,2]在第2行进行二分搜索,因此在第12行包含1个障碍{12}.我们还在[0,2]第2列进行二元搜索,因此在第8列包含障碍物{8}.

然后一个4x4平方.为此,我们[0,3]在第3行进行二进制搜索{}.对于[0,3]第3栏 - {}.

然后一个5x5平方.为此,我们[0,4]在第4行进行二进制搜索{4}.对于第[0,4]4栏 - {1,4}.

这是我们实际找到的第一个.在该范围内[0,4],我们4在行和列中找到(我们只需要找到其中一个).所以这表明失败了.

从这里开始,我们在第4列进行二元搜索(再次 - 不是必需的)[0,4].然后二进制搜索列5-8 [0,4],没有找到,所以从位置开始的正方形5,0是下一个可能的候选.

所以从这里我们尝试将平方尺寸增加到5x5,然后工作,然后是6x6和7x7.

然后我们尝试8x8,这是行不通的.

等等.

我知道二进制搜索,但你的工作如何？

所以我们基本上在一组值中进行范围搜索.这很容易做到.首先搜索范围的起始值,然后搜索结束值.如果我们达到相同的点,则范围内没有值.

我们并不关心范围内存在什么价值,只是有没有.