Loading...
Loading...
Loading...
A histogram has n bars, each of width 1. A rectangle must use neighbouring bars and be as tall as the shortest bar in it. Print the area of the largest rectangle.
Example 1
Input
6 2 1 5 6 2 3
Output
10
Bars 5 and 6 give 5 × 2 = 10.
Example 2
Input
3 4 4 4
Output
12
Try the problem first. Open one hint at a time.
Keep bars with rising heights on a stack.
A lower bar ends the taller bars on top. Each ended bar gives one rectangle.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor