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


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;
    }
}
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;
    }
};
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;
};
Largest Rectangle in Histogram