Largest Rectangle in Histogram
HardP2Coding
heights[i] is the height of the i-th bar in a histogram; every bar has width 1. Return the area of the largest rectangle that fits inside the histogram, with its sides aligned to the axes and its base on the baseline.
Example 1
- Input
- heights = [2,1,5,6,2,3]
- Output
- 10
- Why
- Bars of height 5 and 6 give a 5 x 2 rectangle.
Example 2
- Input
- heights = [2,4]
- Output
- 4
Example 3
- Input
- heights = [1]
- Output
- 1
Constraints
- 1 <= heights.length <= 10^5
- 0 <= heights[i] <= 10^4
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 13. ⌘Enter runs, ⌘⇧Enter submits.