169. Largest Rectangle in a Histogram
Challenge1000 ms256 MBSolved by 0%
A histogram is n bars of width 1 standing side by side, each with a given
height.
Find the area of the largest rectangle that fits entirely inside the histogram, and print it. The rectangle may span several bars, but its height is limited by the shortest bar it covers.
For heights [2, 1, 5, 6, 2, 3] the answer is 10, the two bars of heights 5 and 6 give
a rectangle 2 wide and 5 tall.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ height ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer, the area of the largest rectangle that fits inside the histogram.
Input6
2 1 5 6 2 3
Output10
Noteis the worked example from the statement
Input1
5
Output5
Noteis a single bar
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.