我想知道不同的算法,找到点缀着障碍物的二维地图中的最大正方形.
一个例子,哪里o是障碍:
...........................
....o......................
............o..............
...........................
....o......................
...............o...........
...........................
......o..............o.....
..o.......o................
最大的广场将是(如果我们选择第一个):
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxxo..............
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxx...o...........
.....xxxxxxx...............
......o..............o.....
..o.......o................
找到它的最快算法是什么？复杂度最小的那个？
编辑:我知道人们对接受的答案中解释的算法感兴趣,所以我做了一个文档,解释了它,你可以在这里找到它:
https://docs.google.com/document/d/19pHCD433tYsvAor0WObxa2qusAjKdx96kaf3z5I8XT8/edit?usp=sharing
以下是如何在最佳时间量 O(nm)内完成此操作.这是建立在@dukeling的洞察力之上,您永远不需要检查尺寸小于当前已知最佳解决方案的解决方案.
关键是能够构建一个可以在O(1)时间内回答此查询的数据结构.
为了解决这个问题,我们将支持回答一个稍微更难的问题,也在O(1)中.
通过矩形计数问题的答案很容易回答方形存在问题.
要回答矩形计数问题,请注意,如果您已经预先计算了左上角开始的每个矩形的答案,那么您可以通过一种聪明/包含来回答从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平方是否有效.
原生方法:
我们可以简单地检查每个步骤中每个方块的每个可能的单元格,但这是相当低效的.
优化方法:
当增加平方大小时,我们可以在下一行和列上进行二进制搜索,以查看该行/列是否在任何这些位置包含障碍物.
当向右移动时,我们可以对每个下一列进行二进制搜索,以确定该列是否包含任何这些位置的障碍物.
向下移动时,我们可以在目标位置的每个列上执行类似的二进制.
实施说明:
首先,我们需要遍历所有的行和列,并设置包含每个行的障碍位置的数组,我们可以将其用于二进制搜索.
运行时间:
我们进行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,这是行不通的.
等等.
我知道二进制搜索,但你的工作如何？
所以我们基本上在一组值中进行范围搜索.这很容易做到.首先搜索范围的起始值,然后搜索结束值.如果我们达到相同的点,则范围内没有值.
我们并不关心范围内存在什么价值,只是有没有.