Simplest and Easiest Solution ️‍🔥 | O(n) | C++ | ️‍
Intuition\nTo find the largest rectangle in a histogram, we need to determine the largest possible rectangular area that can be formed using consecutive bars. T
# Intuition\nTo find the largest rectangle in a histogram, we need to determine the largest possible rectangular area that can be formed using consecutive bars. The key idea is to efficiently find the next smaller element and the previous smaller element for each bar. Using these, we can compute the width of the rectangle where the current bar is the shortest bar in the rectangle, and thus calculate the maximum area for each bar as the shortest bar.\n\n# Approach\n1. Next Smaller Element (nxt array): Traverse the histogram from right to left. Use a stack to keep track of the indices of the bars. For each bar, pop elements from the stack until you find a bar shorter than the current bar. The index of this shorter bar is stored in the nxt array.\n2. Previous Smaller Element (prev array): Traverse the histogram from left to right. Use a stack to keep track of the indices of the bars. For each bar, pop elements from the stack until you find a bar shorter than the current bar. The index of this shorter bar is stored in the prev array.\n3. Calculate the Maximum Area: For each bar, calculate the width of the rectangle where the current bar is the shortest by using the nxt and prev arrays. The area of the rectangle is the height of the current bar multiplied by the width. Track the maximum area found.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        vector<int>nxt;\n        vector<int>prev;\n        stack<int>s;\n        int n = heights.size();\n        s.push(n);\n        for(int i=n-1;i>=0;i--){\n            while(s.top()!=n && heights[s.top()]>=heights[i]) s.pop();\n            nxt.push_back(s.top());\n            s.push(i);\n        }\n        while(!s.empty()) s.pop();\n        s.push(-1);\n        for(int i=0;i<n;i++){\n            while(s.top()!=-1 && heights[s.top()]>=heights[i]) s.pop();\n            prev.push_back(s.top());\n            s.push(i);\n        }\n        int m=0;\n        for(int i=0;i<n;i++)m = max(m,heights[i] * (nxt[n-1-i]-prev[i]-1));\n        return m;\n    }\n};\n```
['C++']