Description
Given an array of integers heights representing the histogram's bar heights where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Examples
Input:
heights = [2,1,5,6,2,3]Output:
10Explanation:
Stack finds max at indices 2-3 with heights [5,6]. Rectangle width=2, height=min(5,6)=5, area=10.
Input:
heights = [2,4]Output:
4Explanation:
Two options: height 2 spanning both bars (area=4), or height 4 with width 1 (area=4). Max is 4.
Input:
heights = [3,1,3,2,2]Output:
6Explanation:
Indices 2-4 have heights [3,2,2]. Rectangle with min height 2 and width 3 gives area = 6.
Constraints
- •
1 ≤ heights.length ≤ 10⁵ - •
0 ≤ heights[i] ≤ 10⁴