problem:84. 柱状图中最大的矩形

思路：单调栈找出每个元素左边第一个最小值和右边第一个最小值，在枚举一遍，维护答案最大值就好了。

Accode:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> sta;
        vector<int>left,right;
        for(int i=0;i<heights.size();i++){
            right.push_back(i);
            while(sta.size() && heights[sta.top()]>heights[i]){
                right[sta.top()] = i;
                sta.pop();
            }
            sta.push(i);
        }
        while(sta.size()) sta.pop();
        for(int i=0;i<heights.size();i++){
            left.push_back(i);
            while(sta.size() && heights[sta.top()]>=heights[i]){
                sta.pop();
            }
            if(sta.size()) left[i] = sta.top();
            sta.push(i);
        }
        int ans = 0;
        for(int i=0;i<heights.size();i++){
            int l = left[i],r = right[i];
            if(l==i) l = -1;
            if(r==i) r = heights.size();
            ans = max(ans,heights[i]*(r-l-1));
        }
        return ans;
    }
};

时间复杂度：$o(n)$