https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

方案：

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/

 

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

        for i in range(len(heights)):
            while stacks and heights[stacks[-1]] > heights[i]:
                tmp_index = stacks.pop()
                tmp_value = heights[tmp_index]
                tmp_result = tmp_value * (i - stacks[-1] - 1)
                max_value = max(max_value, tmp_result)
            stacks.append(i)
        
        return max_value