Thực hiện thuật toán hình chữ nhật tối đa

Question

Tôi đang cố triển khai Maximum Rectangle Algorithm from Dr. Dobbs (Liệt kê bốn) bằng Python. Nó hoạt động chủ yếu, nhưng một trường hợp cụ thể cho kết quả sai và tôi không thể hiểu tại sao.

Đây là mã nguồn của tôi:

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 

Và đây là kết quả:

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

Như bạn có thể thấy, điểm đầu tiên là sai, nhưng tôi không thể tìm ra ở đâu và tại sao nó đi sai . Thay đổi arr cho kết quả đúng.

Chỉnh sửa: Tôi nhận thấy tôi đã thay đổi giá trị của mảng so với bài viết. Điều này thay đổi so sánh trong update_cache. 0 = xóa và 1 = đặt trước. Tôi đang tìm kết quả (Điểm (X = 0, Y = 1), Điểm (X = 1, Y = 2)).

Answer 1

stack.append cuối nên là:

stack.append((y0, w0))