Largest Rectangle in Histogram最大长方形

题目描述：

给定n个非负整数height[n]，分别代表直方图条的高，每个条的宽设为1，求直方图中面积最大的矩形的面积

题目来源：

http://oj.leetcode.com/problems/largest-rectangle-in-histogram/

题目分析：

维护一个栈，保存直方图条的下标，当当前栈为空或者栈顶的下标所表示的元素不大于当前元素时，入栈，否则出栈，直到可以把当前元素压入栈中

（1）对于当前栈，假设序列为a1, a2,...ai, ai+1, a...栈顶，那么处于ai和ai+1之间的元素一定大于ai+1，如果他们中的最小元素小于等于ai+1，那么它一定在栈中，故栈中处于ai和ai+1之间的元素一定大于ai+1

（2）计算矩形的面积，可以考虑以待计算的元素为中心，向右扩展最远，并且向左扩展最远

（3）出栈时，计算以刚出栈的元素为高的最大矩形，它向左扩展最远到栈中的下一个元素，向右扩展最远到当前元素（因为当前元素比他小）

时间复杂度：O（n）

示例代码：

int maxArea(vector<int> vi) {
    stack<int> st;
    int maxArea = 0, i = 0;

    while(i <= n) {
        if(st.empty() || vi[st.top()] <= vi[i]) {
            st.push(i++);
        } else {
            int tmp = st.top();
            st.pop();
            maxArea = max(maxArea, vi[tmp] * (st.empty() ? i : i - st.top() - 1));
        }
    }
    
    return maxArea;
}