Largest Rectangle in Histogram
HardStack
You are given an array heights describing a histogram: bar i has width 1 and height heights[i], and the bars stand side by side with no gaps.
Find the largest axis-aligned rectangle that fits entirely inside the histogram and return its area. The rectangle can span any run of adjacent bars, but its height cannot exceed the shortest bar in that run.
For a run of bars from index l to r, the best rectangle has area (r - l + 1) * min(heights[l..r]).
Example 1
- Input:
- heights = [1, 2, 3, 4]
- Output:
- 6
- Explanation
- Height 3 across the last 2 bars gives 6, and height 2 across the last 3 bars also gives 6. Using all 4 bars is limited to height 1, giving only 4.
Example 2
- Input:
- heights = [3, 3, 3]
- Output:
- 9
- Explanation
- All bars are equal, so the rectangle can span the whole histogram: 3 * 3 = 9.
Example 3
- Input:
- heights = [2, 0, 2]
- Output:
- 2
- Explanation
- The zero-height bar in the middle splits the histogram, so no rectangle can cross it. The best is a single bar of area 2.
Constraints
- 1 ≤
heights.length≤ 105 - 0 ≤
heights[i]≤ 104