LC 0084 [H] Largest Rectangle in Histogram - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=zx5Sw9130L0&t=519s&ab_channel=NeetCode

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        '''
        \ # can't extend right, must be popped from most recent (top of stack), but can extend left
        / or - # can extend right
        [index extended left, height]
        find max area before popping
        calculate remaining in the stack that can extend to the end
        O(n), O(n)
        '''
        maxArea = 0
        stack = [] # pair: (index, height)
        
        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h: # \
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index # extend index left
            stack.append( (start, h) )
        
        for i, h in stack: # assumed everything remaining can extend to the end
            maxArea = max(maxArea, h * (len(heights) - i))
            
        return maxArea