Largest Rectangle in Histogram Visualization & Animation
Finds the maximum rectangle area in a histogram using a monotonic increasing stack; O(n) time.
## What is it?
Find the area of the largest rectangle that can be formed within a histogram. Each bar has width 1 and a given height. The rectangle must be contiguous.
## How it works
**Monotonic Stack approach:**
- Maintain a stack of bar indices in increasing height order
- For each bar `i`:
- While `heights[i] < heights[stack.top()]` → the top bar is the shortest in a potential rectangle; pop it and compute area: `height * (i - new_top - 1)`
- Push `i`
- Process remaining bars in the stack similarly (use `n` as the right boundary)
- Track the maximum area seen
## When to use
- Histogram area problems (LeetCode 84)
- As a building block for "Maximal Rectangle" in a binary matrix
- Understanding the power of monotonic stacks for "nearest smaller element"
## Key Points
- O(n) time — each bar pushed and popped once
- O(n) space for the stack
- Each popped bar's "span" extends from the new stack top + 1 to the current index − 1
