class Solution {
public:
    int largestRectangleArea(vector<int>& nums) {
        stack<int>res;
        int n = nums.size();
        vector<int>left(n),  right(n);
        for(int i=0;i<n;i++)
        {
            while(!res.empty() && nums[res.top()] >= nums[i])
                res.pop();
            if(res.empty()) left[i] = -1;
            else left[i] = res.top();
            res.push(i);
        }

        res = stack<int>();
        for(int i= nums.size()-1;i>=0;i--)
        {
            while(!res.empty() && nums[res.top()] >= nums[i])
                res.pop();
            if(res.empty()) right[i] = nums.size();
            else right[i] = res.top();
            res.push(i);
        }

        int s = 0;
        for(int i=0;i<nums.size();i++)
            s = max(s, (right[i] - left[i] - 1) * nums[i]);
        return s;
    }
};