柱状图中最大的矩形

问题

原题链接：https://leetcode.cn/problems/largest-rectangle-in-histogram?envType=study-plan-v2&envId=top-100-liked

解法

这是一个很经典的单调栈问题。这题考的基础模型其实就是：在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。仔细一想这道题，无非也是找到最左边第一个低于自己的矩形，和最右边第一个低于自己的矩形，其实这是经典The Next Greater问题

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        stack<int> stk;
        vector<int> left(n);vector<int> right(n,n);

        for(int i=0;i<n;i++){
            while(!stk.empty() && heights[stk.top()]>=heights[i]){
                right[stk.top()]=i;//记录右边低于他的第一位
                stk.pop();
            }

            left[i]= stk.empty()?-1:stk.top();//记录左边低于他的第一位
            stk.push(i);
        }

        int ans=0;
        for(int i=0;i<n;i++){
            ans=max(ans,(right[i]-left[i]-1)*heights[i]);
        }
        return ans;
    }
};