C++ EasyToUnderstad Stack Solution || ⭐⭐⭐
Intuition\n Describe your first thoughts on how to solve this problem. \nwe will consider heights[i] as a length and check both ways how much it extends to both
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe will consider heights[i] as a length and check both ways how much it extends to both ways \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor every heights[i] we will find its next smaller to the right and its next smaller to the left \n\nbecause till all elements are greater around heights[i], heights[i] length can be cut from them and added to its area, this way we calculate breadth of rectangle.\n\nfor every element of heights if we know how much we can extend its area to both sides, we can check for all heights[i] and return the maximum area as answer.\n\n# Complexity\n- Time complexity:O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights){\n        int n=heights.size();\n        vector<int> nsr(n,0);\n        vector<int> nsl(n,0);\n\n        stack<int> s;\n\n        for(int i=n-1;i>=0;i--){\n            while(!s.empty() && heights[i]<=heights[s.top()]){\n                s.pop();\n            }\n            if(s.empty()) nsr[i]=n;\n            else nsr[i]=s.top();\n            s.push(i);\n        }\n\n        while(!s.empty()) s.pop();\n\n        for(int i=0;i<n;i++){\n            while(!s.empty() && heights[i]<=heights[s.top()]){\n                s.pop();\n            }\n            if(s.empty()) nsl[i]=-1;\n            else nsl[i]=s.top();\n            s.push(i);\n        }\n\n        int ans=0;\n\n        for(int i=0;i<n;i++){\n            ans=max(ans, heights[i]*(nsr[i]-nsl[i]-1));\n        }\n        return ans;        \n    }\n};\n```
['Stack', 'C++']