Easy C++ sol with just one traversal
Pre-requisite = Previous smaller element using stack.\n\nIdea :-The idea is to use the concept of next smaller element and previous smaller element, we will mai
**Pre-requisite** = Previous smaller element using stack.\n\n**Idea** :-The idea is to use the concept of next smaller element and previous smaller element, we will maintain the index of previous smaller element in the stack and we can get the next smaller element when we pop the element from the stack as the element is popped only when we encounter a smaller element. If at the end the stack is not empty , then for those elements there was no next smaller element so we can consider the next smaller element to exist at the the index = size of the vector/ array, while the previous smaller element is always just below the element it in the stack given the stack had an element below it, otherwise consider the previous smaller element at -1. \n\n```\nint largestRectangleArea(vector<int>& heights) {\n        int n = heights.size();\n        stack<int> st;\n        int maxArea = 0;\n        \n        for(int i = 0; i<n; i++) {\n            while(!st.empty() && heights[i] <= heights[st.top()]) {\n                int ind = st.top();\n                st.pop();\n                int currArea = heights[ind]*(st.empty() ? i : i - st.top() - 1);\n                maxArea = max(maxArea, currArea);\n            }\n            st.push(i);\n        }\n        \n        while(!st.empty()) {\n            int ind = st.top();\n            st.pop();\n            int currArea = heights[ind]*(st.empty() ? n : n - st.top() - 1);\n            maxArea = max(maxArea, currArea);\n        }\n        return maxArea;\n    }\n```
[]