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:
The largest rectangle has area = 10 units (formed by heights[2] and heights[3]).
Input:
heights = [2,4]Output:
4Explanation:
The largest rectangle is the bar of height 4.
Input:
heights = [3,1,3,2,2]Output:
6Explanation:
The largest rectangle can be formed in multiple ways with area 6: either by taking the last 3 bars (heights 3,2,2) with height 2 and width 3, or by taking bars at indices 0 and 2 cannot form a contiguous rectangle due to the height 1 bar between them. The optimal solution is the rectangle of height 2 spanning the last 3 positions.
Constraints
- •
1 ≤ heights.length ≤ 10⁵ - •
0 ≤ heights[i] ≤ 10⁴