84-柱状图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

---

示例

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

输入: [2,1,5,6,2,3]
输出: 10

---

解法

核心思想：遍历寻找以第i根柱子为最高柱子所能延伸的最大面积

即 找栈顶左右两边第一个比栈顶小的元素，【利用“单调栈”】

巧妙地点：在两侧加上0柱子便于处理边界

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        # 在原柱子两端加上两个高度为0的柱子，便于计算边界
        heights = [0] + heights + [0]
        res = 0
        # 遍历：以第i根柱子为最高柱子所能延伸的最大面积
        # 即   找栈顶左右两边第一个比栈顶小的元素
        for i in range(len(heights)):
            # print(stack)
            # 调整位置
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                res = max(res, (i - stack[-1] - 1) * heights[tmp])
            # 当前元素无论如何也要放进去，不同的只是需不需要pop来调整位置
            stack.append(i)
        return res

---

相关信息

LeetCode：Discussion | Solution