84.md

84 Largest Rectangle in Histogram

Description

link

---

Solution

这个方法算是stack应用的集大成者，找出所有递增的子序列（不一定要连续），求得最大值

---

Code

O(n)

class Solution:
    def largestRectangleArea(self, height):
        """
        :type heights: List[int]
        :rtype: int
        """
        height.append(0)
        # start from 0,end at 0
        stack = [-1]
        res = 0
        for i in range(len(height)):
            while height[i] < height[stack[-1]]:
                h = height[stack.pop()]
                w = i - stack[-1] - 1
                res = max(res, h * w)
            stack.append(i)
        height.pop()
        return res