Largest Rectangle in a Bar Chart
You get an array heights. It describes a bar chart: bar i has width 1 and height heights[i], and the bars stand next to each other with no gaps.
Find the largest area of a rectangle that fits completely inside the bars. The rectangle must be made of whole bars that are next to each other, and its height can be at most the shortest of those bars. Return that area.
If every bar has height 0, return 0.
Hint
For each bar, ask: if this bar is the shortest one in the rectangle, how far can the rectangle reach to the left and to the right? It stops at the first shorter bar on each side. A stack that keeps bar indices in order of increasing height finds those limits for all bars in one pass, in O(n).
Examples
Example 1
- Input:
- [3,1,4,5,2,4]
- Output:
- 8
Bars 2 and 3 have heights 4 and 5. A rectangle of height 4 over both has area 4 * 2 = 8. Height 2 over bars 2 to 5 also gives 2 * 4 = 8.
Example 2
- Input:
- [6,6,6]
- Output:
- 18
All three bars have height 6, so the full width works: 6 * 3 = 18.
Example 3
- Input:
- [0,7,0,2,3]
- Output:
- 7
The single bar of height 7 gives area 7. The bars 2 and 3 together give only 2 * 2 = 4.
Constraints
1 <= heights.length <= 500 <= heights[i] <= 1000
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.