Finding the maximum rectangle under a histogram

September 28, 2017

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

You're given non-negative numbers h[0],…,h[n−1]h[0],…,h[n−1] representing a histogram. Find the maximum area of rectangle beneath it, i.e. maxi≤j(j−i+1)mini≤k≤jh[k]maxi≤j(j−i+1)mini≤k≤jh[k] in O(n)O(n) time.

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

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

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

post by Shen-Fu Tsai