class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        vector<int>left(n,-1);
        vector<int>right(n,n);
        stack<int>stk;
        stk.push(-1);
        for(int i=0;i<n;i++){
            while(1){
                if(stk.top()==-1){
                    left[i]=-1;
                    stk.push(i);
                    break;
                }
                else if(heights[stk.top()]>=heights[i]){
                    stk.pop();
                }
                else if(heights[stk.top()]<heights[i]){
                    left[i]=stk.top();
                    stk.push(i);
                    break;
                }
            }
        }
        stack<int>stk1;
        stk1.push(n);
        for(int i=n-1;i>=0;i--){
            while(1){
                if(stk1.top()==n){
                    right[i]=n;
                    stk1.push(i);
                    break;
                }
                else if(heights[stk1.top()]>=heights[i]){
                    stk1.pop();
                }
                else if(heights[stk1.top()]<heights[i]){
                    right[i]=stk1.top();
                    stk1.push(i);
                    break;
                }
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            int low=(right[i]-1)-(left[i]+1)+1;
            ans=max(ans,low*heights[i]);
        }
        return ans;
    }
};