[HW 4] Largest Rectangle in Histogram #84.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = [] # store (index, height) pairs

        for index, height in enumerate(heights):
            start = index

            while start and stack[-1][1] > height:
                # from index 1 ~
                # when new height is smaller than last element in stack
                # => repeating causes width to expand as elements are popped out
                i, h = stack.pop()
                maxArea = max(maxArea, (index - i) * h)
                start = i # start idx to calculate area is from popped stack element
            stack.append((start, height))

        for index, height in stack: # deal with remainder in stack 
            maxArea = max(maxArea, (len(heights) - index) * height)

        return maxArea

Soohan-Kim / Leetcode

[HW 4] Largest Rectangle in Histogram #84. #48