✅Easy✨||C++ || Beats 100% || With proper Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nWe will use two function next smaller and prev smaller element function and by getting 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe will use two function next smaller and prev smaller element function and by getting that value we will find width and length is properly the height of histogram by simply just multiplying width and length we will get area and at the end using max function we will get maximun area in histogram.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The function largestRectangleArea takes a vector heights representing the heights of bars in a histogram.It initializes variables n to store the size of the heights vector and area to store the maximum area.It declares two vectors next and prev, which will be used to store the indices of the next smaller and previous smaller elements, respectively, for each element in the heights vector.\n\n2. The function then calls the helper functions nextelement and prevelement, which use a stack to find the next smaller and previous smaller elements\' indices for each element in the heights vector.After calculating the next and prev vectors, the function iterates through each element in the heights vector using a for loop.\n\n3. For each element, it calculates the width of the rectangle by subtracting the index of the previous smaller element from the index of the next smaller element and subtracting 1. This width represents the width of the rectangle formed by considering the current element as the height.The height of the rectangle is the value of the current element (heights[i]).\n\n4. The area of the rectangle is then calculated by multiplying the height and width.The function updates the area with the maximum value found so far.\n\n5. Finally, the function returns the maximum area found.\nThe algorithm essentially calculates the area of the largest rectangle that can be formed for each bar in the histogram by considering it as the height and extending it to the left and right until it encounters bars that are lower or of equal height.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(3N) -~= O(N)\n# Code\n```\nclass Solution {\npublic:\nvector<int> prevSmallerElement(vector<int>& input) {\n    stack<int>s;\n    s.push(-1);\n    vector<int> ans(input.size());\n   \n   //left to right-> prev smaller element\n   for(int i =0; i<input.size(); i++) {\n       int curr = input[i];\n\n       //your answer in stack\n       while(s.top() != -1 && input[s.top()] >= curr) {\n           s.pop();\n       }\n\n       //smallelemeent is found h ans store \n       ans[i] = s.top();\n   \n//push the curr elemen t\ns.push(i);\n }\nreturn ans;\n\n}\n\nvector<int> nextSmaller(vector<int> &input) {\n      stack<int>s;\n    s.push(-1);\n    vector<int> ans(input.size());\n   \n   //left to right-> prev smaller element\n   for(int i =input.size()-1; i>=0; i--) {\n       int curr = input[i];\n\n       //your answer in stack\n       while(s.top() != -1 && input[s.top()] >= curr) {\n           s.pop();\n       }\n\n       //smallelemeent is found h ans store \n       ans[i] = s.top();\n   \n//push the curr elemen t\ns.push(i);\n }\nreturn ans;\n}\n    int largestRectangleArea(vector<int>& heights) {\n        //step 1: prevSmaller output\n        vector<int> prev = prevSmallerElement(heights);\n\n        //step 2: nextSmaller call\n        vector<int> next = nextSmaller(heights);\n\n        int maxArea = INT_MIN;\n        int size = heights.size();\n\n        for(int i=0; i<heights.size(); i++) {\n            int length = heights[i];\n           \n           //this is important step in code to ressign value to the size of histogram\n            if(next[i] == -1) {\n                next[i] = size;\n            }\n\n            int width = next[i] - prev[i] -1;\n\n            int area = length*width;\n\n           maxArea = max(maxArea, area);\n        }\n        return maxArea;\n    }\n};\n```
['C++']