I got a DP solution first which is O(n^2). Apparently it is not a optimized one - think about: it is linear value space. There must be O(n) solution.

And yes there is: http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html

It reminds me the mono-queue optimization upon DP - it is said to be even out-of-scope of IOI.. Precisely that is not a typical mono-queue style used. The mono-queue maintanence is tricky: if new height is less than top, we pop out all anti-mono elements and calculate corresponding areas - to make sure the queue is monotonous.

But how to conduct yourself to the wonderland you are longing for? Like this:

O(n^3) solution is direct -> Has duplicated calculation? Use DP -> O(n^2) -> is it linear space? think about MonoQ -> figure out how to maintanent MonoQ -> O(n)

Please keep the animated pictures of the whole procedure in mind. That helps.

TO BE REVISED LATER