直方图中矩形的最大面积 - 为什么我们需要堆栈？

Question

Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram.

核心思路是计算：

R[i] = Area of the largest rectangle with the bar at i is as the smallest bar in the rectangle (i.e. width = H[i]) left[i] = the left most boundary of R[i], which is the leftmost bar greater than H[i]. right[i] = the right most boundary of R[i], which is the rightmost bar greater than H[i].

我知道需要一个堆栈来计算 right 和 left 但 我认为 我能够提供类似的解决方案而不使用堆栈：

def max_area_rect(lst):
    n = len(lst)
    right = [-1] * n
    left = [-1] * n

    right[n - 1] = n
    for i in range(n - 2, -1, -1):
        right[i] = i + 1 if lst[i] > lst[i + 1] else right[i + 1]

    left[0] = -1
    for i in range(1, n):
        left[i] = i - 1 if lst[i - 1] < lst[i] else left[i - 1]

    max_res = -1
    for i in range(n):
        right_len = right[i] - i -1
        left_len = i - left[i] + 1
        h = min(lst[right_len - 1], lst[left_len + 1])
        res = (right_len + left_len) * h
        if res > max_res:
            max_res = res

    return max_res

    # test
    print(max_area_rect([4, 2, 1, 8, 6, 8, 5, 2])) # expected result: 20

所以我的问题是：为什么我们需要堆栈？我的方法有效吗？

Answer 1

你提到的 left[i] 的定义

left[i] = the left most boundary of R[i], which is the leftmost bar greater than H[i]

您在代码中定义的内容

left[i] = i - 1 if lst[i - 1] < lst[i] else left[i - 1]

即如果左侧的柱子更高，则您放置 left[i] = left[i-1]。但是，这里的错误是 left[i-1] 存储了大于 lst[i-1] 而不是 lst[i].

的最左边的索引

例如在您提供的输入序列 6, 8, 5 中，left[i] for 8 不应该包括 6，所以 left[i] 应该是 i 但是left[i] for 5 应该包括 6 和 8，这就是您的代码忽略的内容。

直方图中矩形的最大面积 - 为什么我们需要堆栈？

Maximum area of a rectangle in an histogram - Why do we need stack?

python

algorithm

computer-science