Largest Rectangle in Histogram

Stacks & Monotonic Stacks, problem 7 of 7

Largest Rectangle in Histogram

Hard

LC #84

monotonic stackarray

Not attempted yet

heights describes a histogram: 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 histogram.

Example 1

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: bars 5 and 6 give a
rectangle of height 5, width 2.

Example 2

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

Example 3

Input: heights = [6,2,5,4,5,1,6]
Output: 12
Explanation: height 4 across the
three bars 5,4,5.

Constraints

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

Python

Loading draft…

Test results

10 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 7 hidden

Run examples, then submit all tests.