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.

Test Cases

Input:

2
1
5
1
5
2
3
(int[]) heights = [2,1,5,6,2,3]

Output:

(int) 10

Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stack;
        int maxArea = 0, n = heights.size(), i=0;
        while(i<n) {
            if (stack.empty() || heights[i] >= heights[stack.top()]) {
                stack.push(i++);
            } else {
                int top = stack.top();
                stack.pop();
                int width = stack.empty() ? i : i - stack.top() - 1;
                maxArea = max(maxArea, width*heights[top]);
            }
        }
        while(!stack.empty()) {
            int top = stack.top();
            stack.pop();
            int width = stack.empty() ? n : n - stack.top() - 1;
            maxArea = max(maxArea, width*heights[top]);
        }
        return maxArea;
    }
};
func largestRectangleArea(heights []int) int {
    i, maxArea, n := 0, 0, len(heights)
    var stack []int
    top := -1
    for i < n {
        if len(stack) == 0 || heights[i] >= heights[stack[len(stack) - 1]] {
            stack = append(stack, i)
            i++
        } else {
            top, stack = stack[len(stack)-1], stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] -1
            }
            area := heights[top]*width
            if area > maxArea {
                maxArea = area
            }
        }
    }
    for len(stack) > 0 {
        top, stack = stack[len(stack)-1], stack[:len(stack)-1]
        width := i
        if len(stack) > 0 {
            width = i - stack[len(stack)-1] -1
        }
        area := heights[top]*width
        if area > maxArea {
            maxArea = area
        }
    }
    return maxArea
}
class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int n = heights.length;
        int maxArea = 0;
        int i=0;
        while(i<n) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, heights[top]*width);
            }
        }
        while(!stack.isEmpty()) {
            int top = stack.pop();
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, heights[top]*width);
        }
        return maxArea;
    }
}
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        i, n, maxArea = 0, len(heights), 0
        stack = []
        while i<n:
            if not stack or heights[stack[-1]] <= heights[i]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                width = i if not stack else i-stack[-1]-1
                maxArea = max(maxArea, heights[top]*width)
        while stack:
            top = stack.pop()
            width = i if not stack else i-stack[-1]-1
            maxArea = max(maxArea, heights[top]*width)
        return maxArea
Time Complexity: O(n)
Space Complexity: O(n)