The biggest rectangle inside a histogram

Hard

2000 ms limit256 MB memoryArrays Stacks and queues

Stuck?

Show a hint

Take each bar as the shortest one in its rectangle. The width runs to the nearest shorter bar on each side, and a stack of increasing heights gives you both.

The idea behind this problem

Monotonic stacks: the nearest bigger thing, in one pass

Next in this lesson

Water held between the bars

A histogram is a row of bars, each one unit wide, with the heights given. Find the area of the largest rectangle that fits entirely inside it.

Worked example#

For [2, 1, 5, 6, 2, 3]:

   #
  ##
  ##
  ## #
# ####
######

The best rectangle is two bars wide and five tall, sitting on the 5 and the 6, so the area is 10.

The idea#

Every rectangle is limited by its shortest bar. So instead of hunting for rectangles, take each bar in turn and ask: if this bar is the shortest one, how wide can the rectangle stretch?

It can stretch left until it meets a bar shorter than this one, and right until it meets another. So for each bar you need the nearest shorter bar on each side, and the area is that width times this bar's height.

Both of those are the "nearest smaller" question a monotonic stack answers. Keep a stack of bars whose heights increase from bottom to top. When a new bar is shorter, every taller bar on the stack has just found its right boundary, so pop it and settle its rectangle. Its left boundary is whatever sits below it on the stack, because that is the nearest bar shorter than it.

Adding an imaginary bar of height zero at the end flushes the stack, so no bar is left unsettled.

Constraints#

1 <= n <= 100000
0 <= heights[i] <= 1000000

Input

heights is a count then that many integers.

Output

Print the largest area.

Examples

Input

6
2 1 5 6 2 3

Output

The 5 and the 6 together give a rectangle two wide and five tall.

Input

2
2 4

Output

Four tall and one wide beats two tall and two wide.

Input

5
3 3 3 3 3

Output

Level bars, so the rectangle is the whole histogram.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.