Easy understandable C++ solution || Similar to Leetcode 84 - Largest Rectangle in Histogram
\n\n# Code\n\nclass Solution {\npublic:\n    vector<int> nextSmallerElement(vector<int> &arr){\n        int n = arr.size();\n        vector<int> ans(n);\n      
\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> nextSmallerElement(vector<int> &arr){\n        int n = arr.size();\n        vector<int> ans(n);\n        stack<int> st;\n        st.push(-1);\n\n        for(int i=n-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\n        return ans;\n    }\n\n\n    vector<int> previousSmallerElement(vector<int> &arr){\n        int n = arr.size();\n        vector<int> ans(n);\n        stack<int> st;\n        st.push(-1);\n    \n        for(int i=0; i<n; 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    \n        return ans;\n    }   \n\n\n    int largestRectangleArea(vector<int>& heights) {\n        vector<int> nextSmaller;\n        vector<int> previousSmaller;\n        int n = heights.size();\n\n        nextSmaller = nextSmallerElement(heights);\n        previousSmaller = previousSmallerElement(heights);\n        int maxi = 0;\n\n        for(int i=0; i<n; i++){\n            if(nextSmaller[i] == -1){\n                nextSmaller[i] = n;\n            }\n            int width = nextSmaller[i] - previousSmaller[i] - 1;\n            int area = heights[i] * width;\n            maxi = max(maxi, area);\n        }\n\n        return maxi;\n    }\n\n\n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        vector<vector<int>> v;\n\n        //convert the matrix to int for our shortcut\n        for(int i=0; i<m; i++){\n            vector<int> temp;\n            for(int j=0; j<n; j++){\n                temp.push_back(matrix[i][j] - \'0\');\n            }\n            v.push_back(temp);\n        }\n\n        int area = largestRectangleArea(v[0]);\n        for(int i=1; i<m; i++){\n            for(int j=0; j<n; j++){\n                if(v[i][j] == 0){\n                    v[i][j] = 0;\n                }\n                else{\n                    v[i][j] += v[i-1][j];\n                }\n            }\n            area = max(area, largestRectangleArea(v[i]));\n        }\n\n        return area;\n    }\n};\n```
['Array', 'Stack', 'Matrix', 'Monotonic Stack', 'C++']