Largest Rectangle in a Histogram

heights is a bar chart: bar i has width 1 and height heights[i], and the bars stand side by side. Return the area of the largest rectangle that fits entirely inside the bars.

Constraints

  • 1 ≤ length of heights ≤ 100,000
  • 0 ≤ heights[i] ≤ 10,000

Example 1

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

Height 5 across the bars 5 and 6.

Example 2

Input
heights = [2,4]
Output
4
Why:

Either the bar of 4 alone, or height 2 across both.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –