dsa · hard
Largest Rectangle in Histogram
heights[i] is the height of a bar of width 1 standing on the x-axis at index i. Bars sit side by side. Return the largest area of a rectangle that fits inside the histogram (sides parallel to the axes). The rectangle may span several consecutive bars and is limited by the shortest bar it covers.
Arguments
heights— bar heights of the histogram; heights[i] is the height of bar i (width 1)
Example
heights = [2,1,5,6,2,3]
The bars of height 5 and 6 together give width 2 and height 5, area 10. That is the maximum (the whole range of six bars is limited by height 1, area 6).
[2,4] → width 1 × height 4 = 4 (or width 2 × height 2 = 4).
Constraints
1 <= heights.length <= 10^5 0 <= heights[i] <= 10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [2,1,5,6,2,3] Expected: 10
Example 2
Input: [2,4] Expected: 4