Untitled

#include<stack>
vector<int> nextsmallelement(vector<int> arr, int n){ // a vector containing next
  stack<int> s;                                        // small element for every index
  s.push(-1);
  vector<int> ans(n);
  for(int i=n-1;i>=0;i--){
    int curr=arr[i];
    while(s.top()!= -1 && arr[s.top()]>=curr){ // to avoid arr[-1]
      s.pop();
    }
    ans[i]=s.top();
    s.push(i);    //s now has index
  }
  return ans;

}

vector<int> prevsmallelement(vector<int> arr, int n){
  stack<int> s;
  s.push(-1);
  vector<int> ans(n);
  for(int i=0;i<n;i++){
    int curr=arr[i];
    while(s.top()!= -1 && arr[s.top()]>=curr){
      s.pop();
    }
    ans[i]=s.top();
    s.push(i);    //s now has index
  }
  return ans;
}


 
  int largestRectangle(vector < int > & heights) { 
    int n=heights.size();
    int ansarea=0;
    vector<int> nextsmall(n);
    vector<int> prevsmall(n);
    nextsmall=nextsmallelement(heights,n);
    prevsmall =prevsmallelement(heights,n);


    for(int i=0;i<n;i++){
      if(nextsmall[i]==-1) nextsmall[i]=n;

      int w=nextsmall[i]-prevsmall[i] -1;
      int area= heights[i] * w;
      ansarea=max(area,ansarea);
    }
    return ansarea;
  }