largest_rectangle_in_histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& a)
    {
        //next smaller to left
        //next smaller to right
        int n=a.size();
        stack<pair<int,int>> stk;
        //what can i do while iterating over the stack from right keep track of the
        //smaller element coming
        int area=-1;
        vector<int> width(n);
        for(int i=(n-1);i>=0;i--)//from right to left fill in right vector
            //next smaller element present in right
        {
           while(stk.size()>0&&stk.top().first>=a[i])
           {
               stk.pop();
           }
           if(stk.empty())
           {
               //nothing smaller to this in right
              width[i]=(n-1);
           }
           else
           {
               width[i]=((stk.top().second)-1);
               //ith element ke right[i] tak sare usse bade and barabar
           }
           stk.push(make_pair(a[i],i));
        }
        while(stk.size()>0) stk.pop();
        for(int i=0;i<=(n-1);i++)//from left to right fill in left vector
            //next smaller element present in left
        {
           while(stk.size()>0&&stk.top().first>=a[i])
           {
               stk.pop();
           }
           if(stk.empty())
           {
               //nothing smaller to this in left
               int temp=0;
              width[i]=(width[i]-temp+1);
           }
           else
           {
               int temp=((stk.top().second)+1);
               width[i]=(width[i]-temp+1);
               //ith element ke left[i] tak sare usse bade and barabar
           }
           stk.push(make_pair(a[i],i));
        }
        for(int i=0;i<=(n-1);i++)
        {
          area=max(area,(width[i]*a[i]));
        }
        return area;
    }
};