class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = [] # (index, height)
        
        for i, h in enumerate(heights):
            startIndex = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                startIndex = index
            stack.append((startIndex, h))
            
        
        
        for index, height in stack:
            maxArea = max(maxArea, height * (len(heights) - index))
            
            
        return maxArea
class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] width = new int[n];
        
        for(int i=0; i<n; i++){
            while(!stack1.isEmpty() && heights[stack1.peek()] >= heights[i])
                stack1.pop();
            if(!stack1.isEmpty())
                left[i] = stack1.peek();
            else
                left[i] = -1;
            stack1.push(i);
        }
        
        for(int i=n-1; i>=0; i--){
            while(!stack2.isEmpty() && heights[stack2.peek()] >= heights[i])
                stack2.pop();
            if(!stack2.isEmpty())
                right[i] = stack2.peek();
            else
                right[i] = n;
            stack2.push(i);
        }
        
        for(int i=0; i<n; i++){
            width[i] = right[i] - left[i] - 1;
        }
        int mxArea = 0;
        for(int i=0; i<n; i++){
            mxArea = Math.max(mxArea, width[i] * heights[i]);
        }        
        return mxArea;
    }
}
Largest Rectangle in Histogram
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

&nbsp;
Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.


Example 2:

Input: heights = [2,4]
Output: 4


&nbsp;
Constraints:


	1 &lt;= heights.length &lt;= 105
	0 &lt;= heights[i] &lt;= 104


var largestRectangleArea = function (heights) {
    let maxArea = 0;
    let stack = []; // [[index, height]]

    for (let i = 0; i < heights.length; i++) {
        let start = i;
        while (stack.length != 0 && stack[stack.length - 1][1] > heights[i]) {
            let [index, height] = stack.pop();
            maxArea = Math.max(maxArea, height * (i - index));
            start = index;
        }
        stack.push([start, heights[i]]);
    }
    for (let i = 0; i < stack.length; i++) {
        maxArea = Math.max(
            maxArea,
            stack[i][1] * (heights.length - stack[i][0])
        );
    }
    return maxArea;
};
class Solution {
private:
    vector<int> nextSmallerElement(vector<int>& arr, int n){
        
        stack<int> s;
        s.push(-1);
        vector<int> ans(n);
        
        for(int i = n-1; i>=0 ; i--){
            int curr = arr[i];
            
            while(s.top()!=-1 && arr[s.top()]>=curr){
                s.pop();
            }
            ans[i] = s.top();
            s.push(i);
        }
        return ans;
    }
    vector<int> prevSmallerElement(vector<int>& arr, int n){
        
        stack<int> s;
        s.push(-1);
        vector<int> ans(n);
        
        for(int i = 0; i<n ; i++){
            int curr = arr[i];
            
            while(s.top()!=-1 && arr[s.top()]>=curr){
                s.pop();
            }
            ans[i] = s.top();
            s.push(i);
        }
        return ans;
    }
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int area = 1, ans = INT_MIN;
        
        vector<int> next(n);
        next = nextSmallerElement(heights, n);
        
        vector<int> prev(n);
        prev = prevSmallerElement(heights, n);
        
        for(int i = 0; i<n ; i++){
            int l = heights[i];
            
            if(next[i] == -1){
                next[i] = n;
            }
            int b = next[i] - prev[i] - 1;
            
            area = l*b;
            ans = max(ans,area);
        }
        return ans;
    }
};