Loading problem…
Given an array of integers `heights` where `heights[i]` represents the height of a bar in a histogram (each bar has width 1), find the area of the largest rectangle that can be formed within the histogram. The rectangle must be made up of contiguous bars. For example, given heights = [2,1,5,6,2,3], the largest rectangle has area 10 (formed by the bars at indices 2 and 3 with heights 5 and 6, spanning width 2 at minimum height 5).
Example 1
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The bars at indices 2 and 3 (heights 5 and 6) can hold a rectangle of height 5 and width 2, for an area of 10. No other stretch of bars does better.
Example 2
Input: heights = [2,4]
Output: 4
Explanation: The tall bar alone gives 4 × 1 = 4, and both bars together give 2 × 2 = 4. Either way the largest area is 4.
Example 3
Input: heights = [1]
Output: 1
Explanation: The only bar has height 1 and width 1, so the area is 1.
Maintain a stack of bar indices in increasing height order. When a shorter bar is found, pop taller bars and compute their rectangles — the stack tells us exactly how far left each popped bar can extend.
Run checks all cases above. Submit evaluates all test cases.