Easy Stack Solution using C++
PLS UPVOTE MY SOLUTION IF YOPU LIKE AND COMMENT FOR ANY DISCUSSION\n\n# Approach\nThe nextelement function takes a vector heights and its size n as input. It in
# PLS UPVOTE MY SOLUTION IF YOPU LIKE AND COMMENT FOR ANY DISCUSSION\n\n# Approach\nThe nextelement function takes a vector heights and its size n as input. It initializes an empty stack and a vector ans of size n to store the indices of the next smaller elements. It then iterates through the heights vector from right to left (from the last element to the first).\n\nFor each element in the heights vector, it compares its height with the elements at the top of the stack (using st.top()), and if the element at the top of the stack is greater than or equal to the current element, it pops elements from the stack (until the top element is smaller than the current element).\n\nAfter the while loop, it stores the index of the next smaller element in the ans vector for the current element (ans[i] = st.top()). If there is no smaller element, it stores the value n (one greater than the last index) to indicate that there is no next smaller element for that element.\n\nThe prevelement function works similarly to nextelement but iterates from left to right to find the previous smaller elements for each element in the heights vector.\n\nThe largestRectangleArea function calculates the largest rectangle area in a histogram. It takes a vector heights as input and uses the nextelement and prevelement functions to find the indices of the next smaller and previous smaller elements for each element in the histogram.\n\nIt then iterates through the heights vector and calculates the area of the rectangle for each bar, considering the bar as the height and the width as the difference between the indices of the next smaller and previous smaller elements for that bar.\n\nThe function returns the maximum area found.\n\nThe maximalRectangle function takes a 2D matrix matrix as input. It initializes a vector histogram of size equal to the number of columns in the matrix, and maxi variable to store the maximum area.\n\nIt iterates through each row of the matrix and populates the histogram vector based on the \'1\'s encountered in each column. When a \'0\' is encountered, the height of the histogram for that column is reset to 0.\n\nFor each row, it calculates the largest rectangle area in the histogram (representing the consecutive \'1\'s encountered so far) using the largestRectangleArea function.\n\nThe function updates maxi with the maximum area found.\n\nFinally, the function returns the maximum area, which represents the largest rectangle area formed by \'1\'s in the binary matrix.\n\nThe approach efficiently uses the concept of histograms and the largest rectangle area calculation to solve the maximalRectangle problem for a binary matrix, resulting in an overall time complexity of O(M * N), where M is the number of rows and N is the number of columns in the matrix.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:0(N*(M+N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:0(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\nvector<int> nextelement(vector<int>& heights, int n )\n{\n    stack<int>st;\n    st.push(-1);\n    vector<int>ans(n);\n    for(int i =n-1;i>=0;i--)\n    {\n        int curr= heights[i];\n        while(st.top()!=-1 && heights[st.top()]>=curr)\n        {\n            st.pop();\n        }\n        if(st.top()==-1)\n        {\n            ans[i]=n;\n        }\n        else\n        {\n            ans[i]=st.top();\n        }\n    st.push(i);\n    }\n    return ans;\n}\n\nvector<int> prevelement(vector<int>& heights, int n )\n{\n    stack<int>st;\n    st.push(-1);\n    vector<int>ans(n);\n    for(int i =0;i<n;i++)\n    {\n        int curr= heights[i];\n        while(st.top()!=-1 && heights[st.top()]>=curr)\n        {\n            st.pop();\n        }\n    ans[i]=st.top();\n    st.push(i);\n    }\n    return ans;\n}\n\n int largestRectangleArea(vector<int>& heights) {\n       int n =heights.size();\n       int area= INT_MIN;\n       vector<int>next=nextelement(heights,n); \n       vector<int>prev=prevelement(heights,n); \n       for(int i =0;i<n;i++)\n       {\n           int l = heights[i];\n           int b = next[i]-prev[i]-1;\n           int newarea= l*b;\n           area=max(area,newarea);\n       }\n       return area;\n    }\n\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        vector<int>histogram(matrix[0].size(),0);\n        int maxi= INT_MIN;\n        \n        for(int i = 0;i<matrix.size();i++)\n        {\n            for(int j= 0 ;j<histogram.size();j++)\n            {\n                if (matrix[i][j]==\'1\')\n                {\n                    histogram[j]++;\n                }\n                else\n                {\n                    histogram[j]=0;\n                }\n            }\n            maxi=max(maxi,largestRectangleArea(histogram));\n        }\n        return maxi;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Stack', 'C++']