84. 柱状图中最大的矩形

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;
    }
};
单调栈练习
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容