84. 柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
难度：困难

描述：
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

提示：
n: [1, 10000]

题解

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        ret = 0
        stk = []
        for i in range(n):
            while stk and heights[stk[-1]] > heights[i]:
                temp = stk.pop()
                l = i - stk[-1] - 1 if stk else i
                ret = max(ret, l * heights[temp])
            stk.append(i)
        while stk:
            temp = stk.pop()
            l = n - stk[-1] - 1 if stk else n
            ret = max(ret, l * heights[temp])
        return ret