Largest Rectangle in Histogram – Solution & Complexity

def largest_rectangle_area(heights):
    stack = []  # indices of increasing bars
    best = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    n = len(heights)
    while stack:
        height = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        best = max(best, height * width)
    return best

def largest_rectangle_area(heights):
    stack = []
    best = 0
    for i, h in enumerate(heights + [0]):  # sentinel flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    return best