Largest Rectangle In Histogram | Monotonic Stack

Given an array of integers heights representing the height of bars in a histogram, find the largest rectangle that can fit inside the histogram.

Parameter

• heights: A list of integer representing the height of each bar in the histogram. Each bar has a width of 1.

Result

• The area of the largest rectangle that can fit inside the histogram.

Example

Example 1

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

Output: 10

Explanation:

Constraints

• 1 <= len(heights) <= 10^5
• 1 <= heights[i] <= 10^4

Try it yourself

Solution