Largest Rectangle in a Histogram
HardPractice library · +30 XPmonotonic stackarrays
A histogram has n bars of width 1 and heights h[0..n-1]. Find the area of the largest rectangle that fits inside the histogram (the rectangle covers a run of consecutive bars and its height is limited by the shortest bar in the run).
Input
Line 1: n
Line 2: n integers h[i]
Output
One integer: the largest area. It can be as large as 10^14, so use 64-bit integers.
Constraints
- 1 <= n <= 100000
- 0 <= h[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB12 hidden tests
Example 1
Input
6 2 1 5 6 2 3
Output
10
The bars of height 5 and 6 make a rectangle of area 10.
Example 2
Input
2 2 4
Output
4
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
6 2 1 5 6 2 3
Example 2 input
2 2 4