Largest Rectangle in Histogram

Problem

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

---

Idea

用一个stack来维护递增的bar的位置，碰到了小于栈顶的bar，则弹栈然后计算面积

• Create an empty stack.
• Start from first bar, and do following for every bar ‘hist[i]‘ where ‘i’ varies from 0 to n-1.
• If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
• If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
• If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

---

Solution

---