436. Biggest Bar Rectangle
A bar chart consists of vertical bars standing side by side on a flat baseline, each bar exactly one unit wide, and bar i has height heights[i]. A designer wants to paste a rectangular sticker onto the chart. The sticker must sit on the baseline and must be completely covered by bars, so it can only span a run of adjacent bars and can be no taller than the shortest bar in that run.
Return the area of the largest sticker that fits. A single bar is a valid run, and the area is the number of adjacent bars used times the sticker height. There can be up to 100,000 bars with heights up to 10,000, so checking every pair of positions is too slow. Bars of height 0 are allowed and simply break up the runs.
Example 1
- Input:
- heights = [6,3,7,7,2,5,9,4]
- Output:
- 16
- Explanation:
The two adjacent 7-bars give 14 and the run 6, 3, 7, 7 limited by the 3 gives 12. Using all eight bars, the shortest one is 2, giving 2 * 8 = 16, which is the best.
Example 2
- Input:
- heights = [8,8,1,8,8,8]
- Output:
- 24
- Explanation:
The three consecutive 8-bars on the right form a 24-area sticker, beating the two on the left and anything crossing the bar of height 1.
Constraints
1 ≤ heights.length ≤ 105
0 ≤ heights[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)