"""
p54 — Largest Rectangle in Histogram (LeetCode 84, HARD).

Given heights[] (non-negative), find the area of the largest axis-aligned rectangle
whose top sits on or below the histogram and whose bottom is on the x-axis.

Implementations:
    largest_rectangle_one_pass  — sentinel + monotonic increasing stack. O(n).
    largest_rectangle_two_pass  — explicit left_smaller / right_smaller arrays. O(n).
    largest_rectangle_each_bar  — for each bar, expand left/right manually. O(n^2) oracle.
    largest_rectangle_brute     — all (l, r) pairs, take min*width. O(n^3) oracle for tiny n.
"""
from __future__ import annotations
import random
from typing import List


def largest_rectangle_one_pass(heights: List[int]) -> int:
    # INVARIANT: stack holds indices; heights at those indices are STRICTLY INCREASING
    # from bottom to top. When a smaller height arrives, pop and resolve.
    H = heights + [0]   # sentinel forces a full flush
    stack: List[int] = []
    best = 0
    for i, h in enumerate(H):
        while stack and H[stack[-1]] > h:
            top = stack.pop()
            # After popping `top`, the bar just below it is the previous strictly-smaller.
            left = stack[-1] if stack else -1
            width = i - left - 1   # exclusive on both ends
            best = max(best, H[top] * width)
        stack.append(i)
    return best


def largest_rectangle_two_pass(heights: List[int]) -> int:
    n = len(heights)
    if n == 0:
        return 0
    left = [-1] * n
    right = [n] * n

    # left[i] = index of previous STRICTLY smaller (or -1)
    stack: List[int] = []
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)

    # right[i] = index of next STRICTLY smaller (or n)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)

    best = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        best = max(best, heights[i] * width)
    return best


def largest_rectangle_each_bar(heights: List[int]) -> int:
    n = len(heights)
    best = 0
    for i in range(n):
        h = heights[i]
        l = i
        while l > 0 and heights[l - 1] >= h:
            l -= 1
        r = i
        while r < n - 1 and heights[r + 1] >= h:
            r += 1
        best = max(best, h * (r - l + 1))
    return best


def largest_rectangle_brute(heights: List[int]) -> int:
    n = len(heights)
    best = 0
    for l in range(n):
        mn = heights[l]
        for r in range(l, n):
            mn = min(mn, heights[r])
            best = max(best, mn * (r - l + 1))
    return best


def edge_cases() -> None:
    # LC canonical
    assert largest_rectangle_one_pass([2, 1, 5, 6, 2, 3]) == 10
    assert largest_rectangle_two_pass([2, 1, 5, 6, 2, 3]) == 10

    # Two bars
    assert largest_rectangle_one_pass([2, 4]) == 4

    # Single bar
    assert largest_rectangle_one_pass([7]) == 7

    # Empty
    assert largest_rectangle_one_pass([]) == 0
    assert largest_rectangle_two_pass([]) == 0

    # All zeros
    assert largest_rectangle_one_pass([0, 0, 0]) == 0

    # Valley
    assert largest_rectangle_one_pass([2, 1, 2]) == 3

    # Plateau
    assert largest_rectangle_one_pass([4, 4, 4, 4]) == 16

    # Strictly increasing
    assert largest_rectangle_one_pass([1, 2, 3, 4, 5]) == 9  # 3*3 = 9 (heights 3,4,5)

    # Strictly decreasing
    assert largest_rectangle_one_pass([5, 4, 3, 2, 1]) == 9  # 3*3 = 9

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(500):
        n = rng.randint(0, 20)
        heights = [rng.randint(0, 10) for _ in range(n)]
        a = largest_rectangle_one_pass(heights)
        b = largest_rectangle_two_pass(heights)
        c = largest_rectangle_each_bar(heights)
        d = largest_rectangle_brute(heights)
        assert a == b == c == d, f"trial {trial}: heights={heights} a={a} b={b} c={c} d={d}"
    print("stress_test: 500 random trials — one_pass, two_pass, each_bar, brute all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")