Stack-largestArea.cpp

#include<iostream>
#include<stack>
#include <vector>
#include <limits.h>
using namespace std;

class Solution{
    private: 
    vector<int> nextSmallerElement(vector<int> &arr, int n){
        stack<int> s;
        s.push(-1);
        vector<int> ans;

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

        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);
        }
        return ans; 
    }//time complexity- O(n)

    public:
    int largestRectangleArea(vector<int> &heights){
        int n = heights.size();

         vector<int> next(n);
         next= nextSmallerElement(heights, n);

         vector<int> prev(n);
         prev= prevSmallerElement(heights, n);
         
         int area= INT_MIN;
         for(int i=0; i<n; i++){
            int l= heights[i];
            if(next[i]==-1){
                next[i]= n;
            }
            int b= next[i]- prev[i] -1;

            int newArea= l*b;
            area= max(newArea, area);
         }

         return area;
    }//time complexity- O(n)
};