Largest Rectangle in Histogram
Given bar heights of a histogram with unit-width bars, find the area of the largest axis-aligned rectangle that fits entirely inside the histogram.
- 1 ≤ n ≤ 10^5
- 0 ≤ heights[i] ≤ 10^4
- For each bar, need the nearest shorter bar on the left and right
- Those boundaries are exactly what a monotonic increasing stack finds
- A bar's rectangle is finalized the moment a shorter bar appears
Asking, for every element, about the nearest element to its left or right that is larger or smaller is a signal to keep a stack whose values are sorted. Each element is pushed once and popped once, and the moment it is popped you know exactly who its "next greater" is: the element doing the popping.
Maintain a stack of indices with non-decreasing heights. When the current bar is shorter than the stack top, pop the top: its height times the width between the new stack top and the current index (exclusive) is a candidate area, because both neighbors are shorter. Append a sentinel height 0 at the end to flush the stack. Every bar is pushed and popped once, so the pass is linear.
- Divide and conquer at the minimum bar runs in O(n log n) average (O(n^2) worst) or O(n log n) with a segment tree for range minimum. Brute force is O(n^2).