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.
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.
post by Shen-Fu Tsai