leetcode-84柱状图中最大的矩形(单调栈)「建议收藏」

全栈程序员站长

发布于 2022-09-22 10:22:19

4750

文章被收录于专栏：全栈程序员必看全栈程序员必看

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

题解对于每一个长方体，找出左边比他小的第一个长方体和右边比他小的第一个长方体，然后遍历求结即可

class Solution { 
   
public:
    int largestRectangleArea(vector<int>& heights) { 
   
        vector<int>left,right;
        stack<int>stk;
        for(int i = 0;i < heights.size();i ++){ 
   
            while(!stk.empty() && heights[stk.top()] >= heights[i])stk.pop();
            if(stk.empty())left.push_back(-1);
            else left.push_back(stk.top());
            stk.push(i);
        }
        while(!stk.empty())stk.pop();
        for(int i = heights.size() - 1;i >= 0;i --){ 
   
            while(!stk.empty() && heights[stk.top()] >= heights[i])stk.pop();
            if(stk.empty())right.push_back(heights.size());
            else right.push_back(stk.top());
            stk.push(i);
        }
        reverse(right.begin(),right.end());
        int res = 0;
        for(int i = 0;i < heights.size();i ++){ 
   
            res = max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
};

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168897.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java