109. Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar heights where each bar has width 1, return the area of the largest rectangle in the histogram.

Input: Integer array heights of length n.

Output: Integer — area of the largest rectangle.

Examples

Input: [2,1,5,6,2,3]
Output: 10
Explanation: Rectangle of height 5 spanning bars 2-3 (width 2). Area=10.

Input: [2,4]
Output: 4
Explanation: Single bar of height 4. Area=4.

Input: [6,2,5,4,5,1,6]
Output: 12
Explanation: Height 4 from index 2 to 4, width 3. Area=12.

Constraints

• 1<=heights.length<=10^5
• 0<=heights[i]<=10^4

Asked by