[栈]LeetCode84. Largest Rectangle in Histogram

不得不说啊，真的是好巧妙，我也是想了好久才想懂。每次把前面大于heights[i]的值能够构成的矩形都求出来，剔出去，从而保证了index中都是高度的升序，并且，index两个柱之间相隔的距离，能够和右端的bar形成矩形。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> index;
        int maxarea = 0;
        
        heights.push_back(0); //为了求解方便，不需要特殊考虑
        for(int i = 0; i < heights.size(); i++) {
            while(!index.empty() && heights[index.top()] >= heights[i]) { //如果前面有高于i点的点，就拿出来求一下矩形面积
                int h = heights[index.top()];
                index.pop();
                
                int fronti = index.empty() ? -1 : index.top();
                maxarea = max(maxarea, h * (i - 1 - fronti));
            }
            index.push(i);
        }
        return maxarea;
    }
};