Largest Rectangle in a Histogram
Advanced
heights[i] is the height of bar i in a histogram; every bar is 1 wide and the bars touch. Return the area of the largest rectangle that fits inside the histogram.
For [2, 1, 5, 6, 2, 3] the answer is 10 (the bars of height 5 and 6 make a rectangle of height 5 and width 2).
The starter code tries every pair of bars. It is correct but too slow for long histograms.
Examples
Example 1
Input:
largest_rectangle([2, 1, 5, 6, 2, 3])
Output:
10
Example 2
Input:
largest_rectangle([2, 4])
Output:
4
Constraints
0 <= len(heights) <= 2000000 <= heights[i] <= 10**9
Theory
Go to TheoryKeywords
dsa-sheetstack-and-queuemonotonic-stack
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.