最大矩形算法实现

Question

我正在尝试使用Python实现Dr. Dobbs的最大矩形算法（第四个列表）。它大多数情况下都能正常工作，但有一个特定的情况会给出错误的结果，而我无法弄清楚原因。

这是我的源代码：

from collections import namedtuple

Point = namedtuple('Point', ('X', 'Y'))

#Y      0  1  2      X
arr = [[0, 0, 0, ], #0
       [1, 0, 0, ], #1
       [0, 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] = 0

def 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, c, 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会得到正确的结果。

编辑：我注意到我已经改变了数组的值，与文章中进行比较时发生了变化。0=清除，1=保留。我正在寻找结果（Point（X=0，Y=1），Point（X=1，Y=2））。

- Harriv

---

相关：在一个N×N的二进制矩阵中找到仅包含零的最大矩形 - jfs

如果有用的话，我基于这个和Dr. Dobbs文献实现了Javascript代码：http://www.codinghands.co.uk/blog/2013/02/javascript-implementation-omn-maximal-rectangle-algorithm/。 - codinghands

Answer 1

最后一个stack.append应该是：

stack.append((y0, w0))

- Harriv

---

不幸的是，即使有这个变化，第一个点仍然是（0, 0）。 - Tcll

为了解释您的运行时过程（我通过IDEA调试器运行了所有内容并监视了更改），一切都发生在while循环内，best_ll 在第一次更新时从(2, 0) 开始，然后在 (0, 0) 返回之前更改为 (1, 0)，而 best_ur 从开始到返回保持不变。 - Tcll

Answer 2

这里有一个优化的解决方案，是从另一个答案修改而来的：（稍微更快和更易读） https://dev59.com/J3E95IYBdhLWcg3wDpmg#30418912

arr = [
    [0, 0, 0, ],
    [1, 0, 0, ],
    [0, 0, 1, ],
]

nrows = len(arr)
ncols = len(arr[0])

w = [[0]*ncols for n in range(nrows)]
h = [[0]*ncols for n in range(nrows)]

skip = 1
area_max = 0
rect = (0,0,0,0)

for r in range(nrows):
    for c in range(ncols):
        if arr[r][c] == skip: continue
        h[r][c] = 1 if not r else h[r-1][c]+1
        w[r][c] = 1 if not c else w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            area = (dh+1)*minw
            if area > area_max[0]:
                area_max = area
                rect = (r-dh, c-minw+1, r, c)

print('area:', area_max)
print('(Point(X=%s, Y=%s), Point(X=%s, Y=%s))'%rect)

结果正是您所需要的：

面积：4
（点（X=0，Y=1），点（X=1，Y=2））

- Tcll