# Finding the maximum rectangle under a histogram

I heard this is classic, but turns out not too hard.

You're given non-negative numbers $$h[0],\ldots,h[n-1]$$ representing a histogram. Find the maximum area of rectangle beneath it, i.e. $$\max_{i\leq j}(j-i+1)\min_{i\leq k\leq j}h[k]$$ in $$O(n)$$ time.

Solution:
Scanning $$h$$ from left to right, we maintain a stack of $$(height, last, cur)$$. $$height$$ is height, $$last$$ is the last $$x$$-coordinate that is equal or above $$height$$, i.e. the leftmost $$x$$-coordinate that covers $$height$$, and $$cur$$ is current $$x$$-coordinate.

The update logic is this. Suppose we're dealing with $$h[i]$$. For each top element with $$height>h[i]$$, replace the current maximum area with $$height\times (i-last)$$ if the latter is larger. Remove the top element no matter what. Then, if (a) the top element has the same $$height$$ as $$h[i]$$, update its $$cur$$ with $$i$$; (b) stack is empty, insert $$(h[i], 0, i)$$; (c) top element has $$cur=l$$, insert $$(h[i], l+1, i)$$.

When we're done scanning, for each $$(height, last, cur)$$ in the stack update maximum area with $$(n-last)height$$ if it's larger.