"""Largest Rectangle in Histogram.

Given bar heights, find area of largest rectangle using contiguous bars.
O(n) via monotonic increasing stack of indices with a sentinel 0.
Brute-force oracle included for verification.
"""
from typing import List


def largest_rectangle_area(heights: List[int]) -> int:
    if not heights:
        return 0
    stack: List[int] = []
    best = 0
    h = list(heights) + [0]
    for i, height in enumerate(h):
        while stack and h[stack[-1]] > height:
            idx = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            area = h[idx] * width
            if area > best:
                best = area
        stack.append(i)
    return best


def _brute(heights: List[int]) -> int:
    n = len(heights)
    best = 0
    for i in range(n):
        mn = heights[i]
        for j in range(i, n):
            mn = min(mn, heights[j])
            area = mn * (j - i + 1)
            if area > best:
                best = area
    return best