【队列 &栈】Leecode-84. 柱状图中最大的矩形

【题目】

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

【题解】

题解1：

• 思路

        单调栈：遍历数组，依次入栈，当不满足单调递增时将栈顶元素弹出，面积为index-栈顶元素位置乘以该元素值

• 复杂度

         时间复杂度：O(n2)，空间复杂度：O(n)

• 代码

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0]
        stack = []
        res = 0

        for index, value in enumerate(heights):
            while stack and heights[index] < heights[stack[-1]]:
                cur = stack.pop()
                width = index - stack[-1] -1
                res = max(res, heights[cur]*width)
            stack.append(index)
        return res