直方图中矩形的最大面积 - 为什么需要使用栈？

Question

考虑下面的问题（和解决方案）：

给定n个非负整数，表示直方图中宽为1的条形的高度，找到直方图中包含的最大面积矩形，即包含在直方图中的最大面积矩形。

关键思想是计算：

R[i]=最大矩形的面积，其中i处的条作为矩形的最小条（即宽度=H[i]）left[i]= R[i]左边界，即大于H[i]的最左边的条right[i]= R[i]右边界，即大于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

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

- socksocket

---

不，这根本就不对。将5改为6，输出结果不会改变。将4改为3，输出结果会变为15。导致20这个结果的计算是res = (1 + 4) * 4，这完全是错误的，但碰巧给出了正确答案。 - user3386109

此外，只需将反向的相同直方图输入您的算法：[2, 5, 8, 6, 8, 1, 2, 4]。您的代码会得出25的结果。顺便说一下，您可以在此处找到各种解决方案：https://dev59.com/h2855IYBdhLWcg3wfUZM。 - PM 2Ring

Answer 1

你提到的left[i]的定义如下：

left[i]是R[i]最左边的边界，即大于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 中，对于 8 的 left[i] 不应包括 6，因此 left[i] 应为 i，但对于 5 的 left[i] 应包括 6 和 8，这是您的代码忽略的内容。

- Shashwat Kumar