【LeetCode】84. 柱状图中最大的矩形

维护一个存储下标的单调栈，入栈时确定左边界，出栈时确定右边界。

代码

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

        int ans=0;

        int i=0;
        while(i<n){
            while(!s.empty()>0 && heights[s.top()]>heights[i]){
                right[s.top()]=i;
                s.pop();
            }
            left[i]=s.empty()?-1:s.top();
            s.push(i);
            i++;
        }

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