单调栈模板

单调栈算法总结

链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

84.柱状图中最大的矩形

int SingleStack(vector<int>& heights) {

    stack<int> single_stack;


    int res=0;
    for(int i=0;i<heights_new.size();i++){

        while(heights[single_stack.top()]>heights_new[i])
        {
            int h=heights[single_stack.top()]; //取第一个作为高
            single_stack.pop();
            int left=single_stack.top(); //取第二个计算宽
            int right=i;
            res=max(res, (right-left-1)*h); 
        }

        single_stack.push(i);
    }
    return res;
}