class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int m = Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
                int height = heights[stack.pop()]; // 3
                int width = i - stack.peek() - 1;
                m = Math.max(m, height * width);
            }
            stack.push(i);
        }

        while (stack.peek() != -1) {
            int height = heights[stack.pop()]; // 3
            int width = heights.length - stack.peek() - 1;
            m = Math.max(m, height * width);
        }
        return m;
    }
}