时间戳

首页 > 解决方案 > 直方图中矩形的最大面积 - 为什么我们需要堆栈？

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

问题描述

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

给定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

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

标签： pythonalgorithmcomputer-science

解决方案

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在您提供的输入中按顺序排列，left[i]对于 8 不应该包含6，所以left[i]应该是i，但是left[i]对于 5 应该包含6以及8这就是您的代码所忽略的。

推荐阅读