84. 柱状图中最大的矩形

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

单调栈练习