ALG-H006HardMonotonic Stack
Largest Rectangle in a Skyline
Given nonnegative heights for adjacent unit-width histogram bars, return the largest rectangular area that fits entirely under the bars.
Contract
input heights: integer[]
return integer
Constraints
- • All heights >= 0
Examples
Example 1
heights = [2, 1, 5, 6, 2, 3]
→ 10
Example 2
heights = [2, 4]
→ 4
5 judge tests (2 shown above). Target complexity: O(n).