Largest Rectangle in Histogram

Hard~40 min

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

Examples

Example 1

Input: heights = [2, 1, 5, 6, 2, 3]

Output: 10

Explanation: The largest rectangle has area = 10 (formed by heights[2]=5 and heights[3]=6, width 2, bounded by heights[4]=2 on the right and heights[1]=1 on the left).

Example 2

Input: heights = [2, 4]

Output: 4

Explanation: The largest rectangle is bar at index 1 with height 4 and width 1.

Constraints

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4
Expected time complexity: O(n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run