Leetcode 84. Largest Rectangle In Histogram

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Note: This chart is known as a histogram.

Examples

Example 1

Input:  heights = [7,1,7,2,2,4]

┌────────────┐ │█ █ │ │█ █ │ │█ █ │ │█ █ █ │ │█ █ █ │ │█ ▓ ▓ ▓ ▓ │ │█ █ ▓ ▓ ▓ ▓ │ └────────────┘ 7 1 7 2 2 4Output: 8 (▓ = largest rectangle, area = 4 width × 2 height)

Example 2

Input:  heights = [1,3,7]

┌──────┐ │ ▓ │ │ ▓ │ │ ▓ │ │ ▓ │ │ █ ▓ │ │ █ ▓ │ │█ █ ▓ │ └──────┘ 1 3 7Output: 7 (▓ = largest rectangle, area = 1 width × 7 height)

Example 3

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

┌────────────┐ │ █ │ │ ▓ ▓ │ │ ▓ ▓ │ │ ▓ ▓ █ │ │█ ▓ ▓ █ █ │ │█ █ ▓ ▓ █ █ │ └────────────┘ 2 1 5 6 2 3Output: 10 (▓ = largest rectangle, area = 2 width × 5 height)

Constraints

• 1 <= heights.length <= 1000
• 0 <= heights[i] <= 1000