Largest Rectangle in Histogram

Q:

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.

T:
To do this in O(n) time, we need to maintain a stack with increasing heights. Traverse through the heights, push its index to the stack if its height is larger than the stack top. Once we see a height lower than the stack top, we can keep popping from the stack and meanwhile calculating the area whose height is determined by the currently popped height, until the stack top's height is higher than the currently traversed height. Since we can make sure the heights between the currently popped height and the stack top are higher than the current height (when pushing each height into the stack, we keep popping the stack as long as the top is higher than the currently traversed height), and the heights between the currently popped height and the currently traversed height are higher than the currently popped height (the heights in the stack is increasing), we can use the index of the stack top and the currently traversed height to determine the width of the area. If the area is larger than seen, we record it as a new record.

A:

class Solution {
public:
    int largestRectangleArea(vector< int > &height) {
        height.push_back(0);
        int area = 0;
        stack st;
        for(int i=0; i < height.size(); i++) {
            if(st.empty() || height[st.top()] < height[i] ) {
                st.push(i);
            } else {
                int tmp = st.top();
                st.pop();
                area = max(area, height[tmp]*(st.empty()?i:(i-st.top()-1)));
                i--;
            }
        }
        return area;
    }
};