Problem
A histogram has bars of width 1 with the given heights. Find the area of the largest rectangle that lies entirely within the bars. A monotonic stack gives an O(n) solution.
Implement largest_rectangle(heights).
Input
heights: Bar heights from left to right.
Output
Return the largest area.
Constraints
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 1,000,000,000
Examples
Input:
heights = [2, 1, 5, 6, 2, 3]
Expected output:
expected = 10Input:
std::vector<long long> heights = {2, 1, 5, 6, 2, 3};
Expected output:
long long expected = 10;Input:
long[] heights = new long[] {2, 1, 5, 6, 2, 3};
Expected output:
long expected = 10;Explanation
Bars 5 and 6 together give a 2-wide rectangle of height 5: area 10.
Input:
heights = [4]
Expected output:
expected = 4Input:
std::vector<long long> heights = {4};
Expected output:
long long expected = 4;Input:
long[] heights = new long[] {4};
Expected output:
long expected = 4;Explanation
A single bar of height 4 has area 4.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
The best rectangle for a bar depends on how far it can extend before a shorter bar blocks it.
Hint 2
Use a monotonic increasing stack to find each bar’s nearest smaller bar on both sides.
Hint 3
Don’t forget bars that never get popped until the end, and handle equal heights consistently.
Expected complexity
O(n) time, O(n) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.