leetcode 84.柱状图中最大的矩形 单调栈应用

题目描述

柱状图中最大的矩形 原题链接

思路

首先，要想找到第 $i$ 位置最大面积是什么？（这是本题的关键点，要知道怎么去计算面积！）

是以i 为中心，向左找第一个小于 $heights[i]$ 的位置 $lef{t}_i$；向右找第一个小于于 $heights[i]$ 的位置 $righ{t}_i$，即最大面积为 $heights[i]\ast (righ{t}_i-lef{t}_i-1)$，如下图所示：

那么如何找到每个位置$i$的$lef{t}_i$和 $righ{t}_i$呢？
这里我们利用单调栈的思想就行，可以实现$O(n)$的复杂度。
直接看代码

代码

class Solution {
    
public:
    int largestRectangleArea(vector<int>& heights) {
    
        vector<int> left,right;

        stack<pair<int,int>> s;
        //求lefti
        for(int i=0;i<heights.size();i++)
        {
    
            while(!s.empty()&&s.top().second>=heights[i])
                s.pop();
            if(s.empty())
                left.push_back(-1); //如果找不到左边第一个比它小的，说明它是最小的，那直接拉到-1
            else
                left.push_back(s.top().first);
            s.push({
    i,heights[i]});
        }

        while(!s.empty()) s.pop();  //清空栈
        //求righti
        for(int i=heights.size()-1;i>=0;i--)
        {
    
            while(!s.empty()&&s.top().second>=heights[i])
                s.pop();
            if(s.empty())
                right.push_back(heights.size());//如果找不到右边第一个比它小的，说明它是最小的，那直接拉到n
            else
                right.push_back(s.top().first);
            s.push({
    i,heights[i]});
        }
        reverse(right.begin(),right.end()); //答案得逆置一下

        int res=0;
        for(int i=0;i<heights.size();i++)
            res=max(res,(right[i]-left[i]-1)*heights[i]); //求可能的最大面积
        return res;
    }
};