84. 柱状图中最大的矩形-526互联

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        vector<int> l=vector<int>(h.size());
        vector<int> r=l;
        stack<int> stk;
        int res=0;
        //初始化l和r数组,分别记录左右两边小于h[i]的下标
        for(int i=0;i<h.size();i++)
        {
            while(stk.size()&&h[i]<=h[stk.top()])
                stk.pop();
            if(!stk.size())  l[i]=-1;//没有比它小的数
            else l[i]=stk.top();
            stk.push(i);
        }
        stk=stack<int> ();
        for(int i=h.size()-1;i>=0;i--)
        {
            while(stk.size()&&h[i]<=h[stk.top()])
                stk.pop();
            if(!stk.size())  r[i]=h.size();//没有比它小的数
            else r[i]=stk.top();
            stk.push(i);
        }
        //枚举每个长度
        for(int i=0;i<h.size();i++)
            res=max(h[i]*(r[i]-l[i]-1),res);
        return res;
    }
};