hardStack / QueuePure DSA~38 min
Max Histogram Capacity
Per-minute provisioned capacity is drawn as a bar chart. The largest solid rectangle that fits under the bars is the biggest sustained capacity block you could have reserved. Find its area.
Problem
Given an array heights representing the heights of bars of unit width, return the area of the largest rectangle that fits entirely within the histogram.
Input
An array heights of n non-negative integers (1 ≤ n ≤ 10^5), 0 ≤ heights[i] ≤ 10^4.
Output
An integer — the maximum rectangle area.
Constraints
- A rectangle spans a contiguous range and is bounded by the minimum bar in it
- Target O(n) with a monotonic stack
- 1 ≤ n ≤ 100,000
Examples
Example 1
Input
heights = [2,1,5,6,2,3]
Output
10
Bars 5 and 6 form a 5×2 = 10 rectangle.
Example 2
Input
heights = [2,4]
Output
4
The bar of height 4 alone (or 2×2) gives area 4.