✅C++ 100% || Worst to Best approaches with explanation || Easy to understand.
Read the below solutions to understand the logic.\n\nPlease upvote if you like it\n\nSolution 1: Brute Force Approach (TLE)\n\nIntuition: The intuition behind t
**Read the below solutions to understand the logic.**\n\n***Please upvote if you like it***\n\n**Solution 1: Brute Force Approach (TLE)**\n\n**Intuition:** The intuition behind the approach is taking different bars and finding the maximum width possible using the bar.\n\n![image](https://assets.leetcode.com/users/images/52a26c24-4a05-4a06-8b08-a364b969549d_1663241771.5117555.png)\n\n**~Time Complexity: O(N*N )** \n\n**~Space Complexity: O(1)**\n\n**Code:-**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int n=heights.size();\n        int maxArea = 0;\n        \n        for (int i = 0; i < n; i++) {\n            int minHeight = INT_MAX;\n            for (int j = i; j < n; j++) {\n                minHeight = min(minHeight, heights[j]);\n                maxArea = max(maxArea, minHeight * (j - i + 1));\n            }\n        }\n        \n        return maxArea;\n    }\n};\n```\n\n**Solution 2: Optimised Approach ( 100% Accepted )**\n\n**Intuition:** The intuition behind the approach is the same as finding the smaller element on both sides but in an optimized way using the concept of the next greater element and the next smaller element.\n\n**Approach: **\n\n1. Steps to be done for finding Left smaller element\n2. Steps to be done for finding the Right smaller element\n3. After finding the right smaller and left smaller of each subsequent array elements, after that find area for each bar using this formuula\n\n\t![image](https://assets.leetcode.com/users/images/bdd608ad-1db0-4850-bac1-b81fbb0fc8b8_1663242227.7100823.png)\n\t\n4. At the end return the maximum area.\n\n**Dry run:-**\n\n![image](https://assets.leetcode.com/users/images/4092b4bc-4a43-4402-9b71-40cb98fbdff5_1663259833.031889.jpeg)\n\n\n**~Time Complexity: O( N )**\n\n**~Space Complexity: O(3N) where 3 is for the stack, left small array and a right small array**\n\n**Code:**\n```\nclass Solution {\npublic:\n    vector<int> nextSmallerElementIndex(vector<int>& heights,int n){\n        stack<int> st;\n        vector<int> res(n);\n        st.push(-1);\n        for(int i=n-1;i>=0;i--){\n            int curr=heights[i];\n            while(st.top()!=-1 && heights[st.top()]>=curr){\n                st.pop();\n            }\n            res[i]=st.top();\n            st.push(i);\n        }\n        return res;\n    }\n    \n    vector<int> prevSmallerElementIndex(vector<int>& heights,int n){\n        stack<int> st;\n        vector<int> res(n);\n        st.push(-1);\n        for(int i=0;i<n;i++){\n            int curr=heights[i];\n            while(st.top()!=-1 && heights[st.top()]>=curr){\n                st.pop();\n            }\n            res[i]=st.top();\n            st.push(i);\n        }\n        return res;\n    }\n    int largestRectangleArea(vector<int>& heights) {\n        int n=heights.size();\n        //Storing next smaller element index\n        vector<int> next=nextSmallerElementIndex(heights,n);\n        //Storing prev smaller element index\n        vector<int> prev=prevSmallerElementIndex(heights,n);\n        \n        int ans=INT_MIN;\n        for(int i=0;i<n;i++){\n            int l=heights[i];\n            if(next[i]==-1) next[i]=n;\n            int b=next[i]-prev[i]-1;\n            ans=max(ans,l*b);\n        }\n        return ans;\n    }\n};\n```\n\n
['Stack', 'C', 'Monotonic Stack', 'C++']