Monotonic Stack
LC #84Hard
Largest Rectangle in Histogram
Monotonic Stack
GoogleAmazonMetaBloombergProblem
Find the area of the largest rectangle that can be formed in a histogram.
arraystack
Constraints
- ›1 ≤ n ≤ 10⁵
- ›0 ≤ heights[i] ≤ 10⁴
Example
Input
heights = [2, 1, 5, 6, 2, 3]Output
10Why
Largest rectangle uses bars at index 2 and 3 (heights 5,6): width=2, height=5 → area=10