198. Largest Rectangle in a Histogram
HardMonotonic Stack
Bars of width 1 have the given heights. Print the area of the largest rectangle that fits under the histogram.
Input format
Line 1: n Line 2: n heights
Output format
The largest area.
Example 1
Input
6 2 1 5 6 2 3
Output
10
Example 2
Input
2 2 4
Output
4
Constraints
1 ≤ n ≤ 10⁵ 0 ≤ heights ≤ 10⁴
Read input from standard input and print the answer to standard output. Your code is judged against 6 test cases, most of them hidden.
Loading the MyLoginn IDE…