Largest Rectangle in Histogram

Hard

Problem

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.

Constraints

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

Examples

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

Output: 10

The largest rectangle is formed using bars at indices 2 and 3 (heights 5 and 6), with width 2 and height 5, giving area = 10 units.

Input: heights = [2,4]

Output: 4

The largest rectangle is the single bar of height 4 with width 1, giving area = 4 units.

Loading...

Loading Python...