Largest Rectangle in Histogram
You are given an array heights describing a histogram: bar i has height heights[i] and width 1, and the bars stand side by side. Find the area of the largest axis-aligned rectangle that fits entirely inside the histogram — it may span several consecutive bars, but its height is capped by the shortest bar it covers.
Up to 10^5 bars with heights up to 10^4, so the O(n^2) approach of trying every bar-range is too slow; the expected solution is O(n) with a stack.
Examples
- Input:
- heights = [2,1,5,6,2,3]
- Output:
- 10
The best rectangle spans the bars of height 5 and 6 with height 5: area 5 * 2 = 10. Spanning heights [5,6,2,3] would cap the height at 2 for area 8; the full array caps at 1 for area 6.
- Input:
- heights = [2,4]
- Output:
- 4
Either the bar of height 4 alone (area 4) or both bars at height 2 (area 4). Both tie at 4.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.