EASY C++ CODE || zarur dkhooo
Intuition\nThis question links the concept of several questions, for example: \n- Finding next smaller element\n- Finding Previous smaller element\n- Histogram 
# Intuition\nThis question links the concept of several questions, for example: \n- Finding next smaller element\n- Finding Previous smaller element\n- Histogram area problem.\nSo we will be just writting 3 seperate functions for each set of problem mentioned above and use these functions in our current working function.\n\n---\n\n# Complexity\n\n- Time complexity:\nO(NXN)\n\n- Space complexity:\nO(N), since we have created vectors.\n\n---\n\n\n\n# Code\n```\nclass Solution {\npublic:\n     vector<int> prev(vector<int> v,int n){\n         vector<int> ans(n);\n         stack<int> s;\n         s.push(-1);\n         for(int i=0;i<n;i++){\n        int curr=v[i];\n        while(s.top()!=-1 && v[s.top()]>=curr){\n            s.pop();\n        }\n        //top me hi ans h;\n         ans[i]=s.top();\n         s.push(i);\n         }\n         return ans;\n     }\n\n     vector<int> next(vector<int> v,int n){\n         vector<int> ans(n);\n         stack<int> s;\n           s.push(-1);\n         for(int i=n-1;i>=0;i--){\n        int curr=v[i];\n        while(s.top()!=-1 && v[s.top()]>=curr){\n            s.pop();\n        }\n        //top me hi ans h;\n         ans[i]=s.top();\n         s.push(i);\n         }\n         return ans;\n     }\n\n    int maxHisto(vector<int> v){\n        int nt=v.size();\n        vector<int> p(nt);\n        p=prev(v,nt);\n        vector<int> n(nt);\n        n=next(v,nt);\n        int sum=INT_MIN;\n        for(int i=0;i<nt;i++){\n          if(n[i]==-1){\n              n[i]=nt;\n          }\n        int a= v[i]*(n[i]-p[i]-1);\n        sum=max(a,sum);\n        }\n        return sum;\n    }\n    int maximalRectangle(vector<vector<char>>& matrix) {\n       vector<vector<int>> v(matrix.size());\n       for(int i=0;i<matrix.size();i++){\n           for(int j=0;j<matrix[i].size();j++){\n               if(matrix[i][j]==\'0\')\n  v[i].push_back(0);\n  else v[i].push_back(1);\n           }\n       } \n       int first= maxHisto(v[0]);\n     for(int i=1;i<v.size();i++){\n        for(int j=0;j<v[i].size();j++){\n            if(v[i][j]!=0){\n                v[i][j]=v[i-1][j]+v[i][j];\n            }\n            else v[i][j]=0;\n        }\n        int a=  maxHisto(v[i]);\n        first= max(first,a);\n     }\nreturn first;\n    }\n};\n```
['Stack', 'C++']