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
LeetCode "Largest Rectangle in Histogram" - TRICKY MONO-QUEUE,布布扣,bubuko.com
LeetCode "Largest Rectangle in Histogram" - TRICKY MONO-QUEUE
原文：http://www.cnblogs.com/tonix/p/3913807.html