動機

Monotonic Stack在pop時當下的狀態是

1 2 3 .left. 7 .right. 2

right的數字大小一定是大於7!! left的數字一定是等於7

這樣就可以形成一個閉區間，這也讓這題變成經典題

Problem

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 1:

Input: heights = [2,1,5,6,2,3]Output: 10Explanation: The above is a histogram where width of each bar is 1.The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]Output: 4

 

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104

Sol

class Solution:
    def largestRectangleArea(self, hs: List[int]) -> int:
        ret = 0
        stk = [] # [end of seg, len]
        for i,n in enumerate(hs+[0]):
            while stk and hs[stk[-1]] >= n:
                j = stk.pop()
                if stk:
                    ret = max(ret, hs[j]*(i-stk[-1]-1))
                else:
                    ret = max(ret, hs[j]*(i))
            stk += i,
        return ret