C++ | Stack | Next Smaller Element
\nclass Solution {\npublic:\n    vector<int> nextSmallerRight(vector<int> heights, int n){\n        vector<int> res(n);\n        stack<int> st;\n        \n     
```\nclass Solution {\npublic:\n    vector<int> nextSmallerRight(vector<int> heights, int n){\n        vector<int> res(n);\n        stack<int> st;\n        \n        for(int i=n-1; i>=0; i--){\n            while(!st.empty() && heights[st.top()]>=heights[i])\n                st.pop();\n            if(st.empty())\n                res[i] = -1;\n            else\n                res[i] = st.top();\n            st.push(i);\n        }\n        return res;\n        \n    }\n    vector<int> nextSmallerLeft(vector<int> heights, int n){\n        vector<int> res(n);\n        stack<int> st;\n        \n        for(int i=0; i<n; i++){\n            while(!st.empty() && heights[st.top()]>=heights[i])\n                st.pop();\n            if(st.empty())\n                res[i] = -1;\n            else\n                res[i] = st.top();\n            st.push(i);\n        }\n        return res;\n        \n    }\n    int largestRectangleArea(vector<int>& heights) {\n        int n = heights.size();\n        \n        vector<int> leftSmaller(n), rightSmaller(n);\n        \n        rightSmaller = nextSmallerRight(heights,n);\n        leftSmaller = nextSmallerLeft(heights,n);\n\n        \n        int res = INT_MIN;\n        \n        for(int i=0; i<n; i++){\n            int left = leftSmaller[i];\n            int right = rightSmaller[i];\n            int  w;\n            \n            if(left==-1) left = -1;\n            if(right==-1) right = n;\n            \n            w = (right-1)-(left+1)+1;\n            res = max(res,heights[i]*w);\n        }\n        \n        \n        return res;\n    }\n};\n\n```
['Stack', 'C']