stack || cpp || similar to max area in histogram
Intuition\n Describe your first thoughts on how to solve this problem. \n# Please upvote the solution if you like it.\n\n# Approach\n Describe your approach to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n# **Please upvote the solution if you like it.**\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe solution uses the concept of histogram where the heights of each column are taken as bars of the histogram. Then, the problem is reduced to finding the largest rectangle area in the histogram.\n\nThe code first defines two helper functions nextSmaller() and prevSmaller() that return the indices of the next smaller and previous smaller element to each element of a given array. These functions use a stack to store the indices of the elements in a decreasing order of their values. The top of the stack always stores the index of the next smaller or previous smaller element.\n\nThen, the maxAreaHistogram() function takes an array and returns the maximum area of the rectangle that can be formed using the histogram of the heights of the bars of the histogram. It uses the nextSmaller() and prevSmaller() functions to calculate the next and previous smaller elements\' indices for each element in the array and then calculates the maximum area of the rectangle using the formula area = length * width, where length is the height of the current element, and width is the distance between the next smaller and previous smaller element indices.\n\nFinally, the maximalRectangle() function takes the binary matrix as input, converts it into an array of integers, and calculates the maximum area of the rectangle by iterating over each row of the matrix and updating the array of heights for each row. The maximum area is returned as the output.\n\nOverall, the code is an implementation of the histogram-based approach to find the maximal rectangle area in a binary matrix.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m*n) where m and n are the dimensions of the input matrix.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m*n)\n\n# Code\n```\nclass Solution {\nprivate:\n    vector<int> nextSmaller(vector<int> &arr,int n){\n        stack<int> st;\n        vector<int> ans(n);\n        st.push(-1);\n        for(int i=arr.size()-1;i>=0;i--){\n            while(st.top()!=-1 && arr[st.top()]>=arr[i]){\n                st.pop();\n            }\n            ans[i]=st.top();\n            st.push(i);\n        }\n        return ans;\n    }\n    vector<int> prevSmaller(vector<int> &arr,int n){\n        stack<int> st;\n        vector<int> ans(n);\n        st.push(-1);\n        for(int i=0;i<arr.size();i++){\n            while(st.top()!=-1 && arr[st.top()]>=arr[i]){\n                st.pop();\n            }\n            ans[i]=st.top();\n            st.push(i);\n        }\n        return ans;\n    }\n    int maxAreaHistogram(vector<int> &arr){\n        int n = arr.size();\n        vector<int> next(n);\n        vector<int> prev(n);\n        next = nextSmaller(arr,n);\n        prev = prevSmaller(arr,n);\n        int area = 0;\n        for(int i=0;i<arr.size();i++){\n            int length = arr[i];\n            if(next[i]==-1){\n                next[i]=n;\n            }\n            int width = next[i]-prev[i]-1;\n            area = max(area,(length*width));\n        }\n        return area;\n    }\npublic:\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        ios_base::sync_with_stdio(false);\n        vector<vector<int>> mat;\n        for(int i=0;i<matrix.size();i++){\n            vector<int> v;\n            for(int j=0;j<matrix[i].size();j++){\n                if(matrix[i][j]==\'1\'){\n                    v.push_back(1);\n                }\n                else{\n                    v.push_back(0);\n                }\n            }\n            mat.push_back(v);\n        }\n        int n = mat.size();\n        int area = maxAreaHistogram(mat[0]);\n        for(int i=1;i<n;i++){\n            for(int j=0;j<mat[i].size();j++){\n                if(mat[i][j]!=0){\n                    mat[i][j]+=mat[i-1][j];\n                }\n            }\n            area=max(area,maxAreaHistogram(mat[i]));\n        }\n        return area;\n    }\n};\n```
['C++']