python– 最大矩形算法实现

概述我正在尝试用Python实现Maximum Rectangle Algorithm from Dr. Dobbs(清单4).它主要起作用,但是一个特定情况会给出错误的结果,我无法弄清楚原因.这是我的源代码：from collections import namedtuple Point = namedtuple('Point', ('X', 'Y'))

我正在尝试用Python实现Maximum Rectangle Algorithm from Dr. Dobbs(清单4).它主要起作用,但是一个特定情况会给出错误的结果,我无法弄清楚原因.

这是我的源代码：

from collections import namedtuplePoint = namedtuple('Point',('X','Y'))#Y      0  1  2      Xarr = [[0,],#0       [1,#1       [0,1,#2       ]def area(ll,ur):    if (ll.X < 0) or (ll.Y < 0) or (ur.X < 0) or (ur.Y < 0):        return 0.    return ((ur.X - ll.X) + 1) * ((ur.Y - ll.Y) + 1)def update_cache(a,c,x):    M = len(a[0])    N = len(a)    for y in range(M):        if a[x][y] == 0:            c[y] = c[y] + 1        else:            c[y] = 0def mrp(a):    best_ll = Point(-1,-1)    best_ur = Point(-1,-1)    M = len(a[0])     N = len(a)    c = [0 for x in range(M + 1)]    stack = []    for x in range(N-1,-1,-1):        update_cache(a,x)                wIDth = 0        for y in range(M + 1):            if c[y] > wIDth:                stack.append((y,wIDth))                                wIDth = c[y]            if c[y] < wIDth:                while True:                    y0,w0 = stack.pop()                    if (wIDth * (y - y0)) > area(best_ll,best_ur):                        best_ll = Point(x,y0)                        best_ur = Point(x + wIDth - 1,y - 1)                    wIDth = w0                    if (c[y] >= wIDth):                        break                wIDth = c[y]                 if wIDth == 0:                    stack.append((y0,wIDth))    return best_ll,best_ur

这是结果：

>>> mrp(arr)(Point(X=0,Y=0),Point(X=1,Y=2))

正如你所看到的,第一点是错误的,但我无法弄清楚它出错的地点和原因.更改arr会给出正确的结果.

编辑：我注意到与文章相比,我已经更改了数组的值.这会更改update_cache中的比较. 0 =清除,1 =保留.我正在寻找结果(Point(X = 0,Y = 1),Point(X = 1,Y = 2)).

最佳答案最后的stack.append应该是：

stack.append((y0,w0))

总结

以上是内存溢出为你收集整理的python – 最大矩形算法实现全部内容，希望文章能够帮你解决python – 最大矩形算法实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。