Maximal Rectangle||using Max area Histogram||Aditya Verma ||C++
\'\'\'\nclass Solution {\npublic:\n    /\n    \n    1.> for every row consider as 1 block of height \n    2.> write maximum are in histogram\n    3.> for MAH \n
\'\'\'\nclass Solution {\npublic:\n    /*\n    \n    1.> for every row consider as 1 block of height \n    2.> write maximum are in histogram\n    3.> for MAH \n        a> create a left array of next smaller element  to left\n        b> create a right array of next smaller to right\n        c> create a width array\n        d>make area array \n        e> take max area\n    4> for all row it return a max area\n    5> take maximu of all returned value\n    6> which is our answer\n    \n    \n    \n    */\n    int MAH(int*arr,int n)\n    {  // next smaller to right side\n        stack<pair<int,int>>stk1;\n        vector<int>right;\n        for(int i=n-1;i>=0;i--)\n        {\n            while(!stk1.empty() and stk1.top().first>=arr[i])\n            {\n                stk1.pop();\n            }\n            if(stk1.empty())\n            {\n                right.push_back(n);\n            }\n            else\n                right.push_back(stk1.top().second);\n            \n            stk1.push({arr[i],i});\n        }\n        reverse(right.begin(),right.end());\n        // next smaller to left side of array\n        \n        stack<pair<int,int>>stk2;\n        vector<int>left;\n        for(int i=0;i<n;i++)\n        {\n            while(!stk2.empty() and stk2.top().first>=arr[i])\n            {\n                stk2.pop();\n            }\n            if(stk2.empty())\n            {\n                left.push_back(-1);\n            }\n            else\n            {\n                left.push_back(stk2.top().second);\n            }\n            stk2.push({arr[i],i});\n        }\n        \n        // make width array and area area;\n        vector<int>area;\n        for(int i=0;i<n;i++)\n        {\n            area.push_back((right[i]-left[i]-1)*arr[i]);\n        }\n        int no=*max_element(area.begin(),area.end());\n        return no;\n        \n    }\n    \n    int maximalRectangle(vector<vector<char>>& matrix) \n    {   if(matrix.empty())\n        return 0;\n        int n=matrix[0].size();\n         \n        \n         int arr[200];\n         vector<int>check;\n         for(int i=0;i<n;i++)\n         {\n             arr[i]=0;\n         }\n        for(int i=0;i<matrix.size();i++)\n        {     int k=0;\n            for(int j=0;j<matrix[0].size();j++)\n            {\n                if(matrix[i][j]==\'1\')\n                {\n                    arr[k]=arr[k]+1;\n                     k++;\n                    \n                }\n                else\n                {\n                    arr[k]=0;\n                    k++;\n                }\n                    \n           }\n           \n          int no=MAH(arr,n);\n           \n          check.push_back(no);\n        }\n        int ans=0;\n        ans=*max_element(check.begin(),check.end());\n        return ans;\n    }\n};
[]