Asked at
Largest Rectangle In Histogram
HardVerifiedMonotonic StackStack~35 min
Given bar heights in a histogram, return the area of the largest rectangle that fits within the bars.
Use a monotonic increasing stack of indices; when a shorter bar arrives, pop and measure the rectangle each popped bar can span.
The input is a single array heights.
Examples
in[2, 1, 5, 6, 2, 3]
out10
The bars at indices 2 and 3 form a 5×2 = 10 rectangle.
in[2, 4]
out4
The bar of height 4 alone gives the largest area.
Constraints
- 1 ≤ heights.length ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
- Target: O(n) time.
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.