Stack C++ - Easy to understand (180ms) [2 Approaches]
Here are two approaches for the problem:\n1. We use previous smaller element and next smaller element and compare those two to \n\tget our desired max rectangle
Here are two approaches for the problem:\n1. We use previous smaller element and next smaller element and compare those two to \n\tget our desired max rectangle area.\n\t\n\tWe have to use two separate functions here to find the previous smaller and next smaller element.\n\tThe algorithm to make it happen is this:\n\t```\n\t curr += ( i - prevSmall[i]-1 ) * heights[i];\n     curr += ( nextSmall[i] - i - 1 ) * heights[i];\n\t```\n\t\n\t**Time Complexity: O(n)\n\tSpace Complexity: O(n)**\n\t\n```\nclass Solution {\nprivate:\n    vector<int> prevSmall;\n    vector<int> nextSmall;\n\n    void previousSmaller(vector<int> heights){\n        stack<int> s;\n        s.push(0);\n        prevSmall.push_back(-1);\n        for(int i=1;i<heights.size();i++){\n            while(s.empty()==false && heights[s.top()]>=heights[i])\n                s.pop();\n            if(s.empty())\n                prevSmall.push_back(-1);\n            else\n                prevSmall.push_back(s.top());\n            s.push(i);\n        }\n    }\n    void nextSmaller(vector<int> heights){\n        stack<int> s;\n        int n = heights.size();\n        s.push(n-1);\n        nextSmall.push_back(n);\n        for(int i=n-2;i>=0;i--){\n            while(s.empty()==false && heights[s.top()]>=heights[i])\n                s.pop();\n            if(s.empty())\n                nextSmall.push_back(n);\n            else\n                nextSmall.push_back(s.top());\n            s.push(i);\n        }\n        //We used the reverse of array to find the next Smaller\n        //So we need to reverse the vector\n        reverse(nextSmall.begin(),nextSmall.end());\n    }\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        nextSmaller(heights);\n        previousSmaller(heights);\n        int res = 0;\n        for(int i=0;i<heights.size();i++){\n            int curr = heights[i];\n            curr += (i-prevSmall[i]-1)*heights[i];\n            curr += (nextSmall[i]-i-1)*heights[i];\n            res=max(curr,res);\n        }\n        return res;\n    }\n};\n```\n\n\n2. We can make the above approach more efficient by using the idea of just previous smaller element\n\tAnd it can be done in a single loop.\n\t**Time Complexity: O(n)\n\tSpace Complexity: O(n)**\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        int res = 0, curr = 0, n = heights.size();\n        stack<int> s;\n        for(int i=0;i<n;i++){\n            while(s.empty() == false && heights[s.top()]>=heights[i]){\n                int top = s.top();\n                s.pop();\n                if(s.empty())\n                    curr = heights[top]*i;\n                else\n                    curr = heights[top]*(i-s.top()-1);\n                res = max(curr,res);\n            }\n            s.push(i);\n        }\n        //For the elements left in the stack\n        while(s.empty() == false){\n                int top = s.top();\n                s.pop();\n                if(s.empty())\n                    curr = heights[top]*n;\n                else\n                    curr = heights[top]*(n-s.top()-1);\n                res = max(curr,res);\n            }\n        return res;\n    }\n};\n```\n\nHope you get it now :)
['Stack', 'C']