84. 柱状图中最大的矩形(hard)

 单调栈：

就是说：固定高度，寻找最长宽度，如何找最长宽度，需要从heights[i] 这一个元素开始向左向右两边寻找heights[j]

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        int n=heights.size();
        vector<int> left(n,0);
        vector<int> right(n,0);
        for(int i=0;i
            while(stk.size()&&heights[stk.top()]>=heights[i])
                stk.pop();
            left[i] = (stk.size()==0? -1:stk.top());
            stk.push(i);
        }
        stk=stack<int>();
        for(int i=n-1;i>=0;i--){
            while(stk.size()&&heights[stk.top()]>=heights[i])
                stk.pop();
            right[i] = (stk.size()==0?n:stk.top());
            stk.push(i);
        }
        int res=0;
        for(int i=0;i
            res=max(res, (right[i]-left[i]-1)*heights[i]);
        }
        return res;
        
    }
};