Leetcode: 84. Largest Rectangle in Histogram

Description

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example

Input: heights = [2,1,5,6,2,3]
Output: 10

Tips

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

code

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        ans = 0
        stack = []
        heights = [0] + heights + [0]
        for i in range(len(heights)):
            while(stack and heights[stack[-1]] > heights[i]):
                j = stack.pop()
                ans = max(ans, (i-stack[-1]-1)*heights[j])
            stack.append(i)
        return ans

总结

1. LC 1856 、1793、907  也可以套用该模版求解出
2.  monotonick stack 用于求解 next great element 比较直观， but next great element 也表示有一个对应的区间！！ 本题就是该区间信息进行求解