class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxare = 0;
        Deque<Integer> sta = new LinkedList<>();
        sta.addLast(-1);
        for(int i = 0;i < heights.length; i++){
            while(sta.peekLast() != -1 && heights[sta.peekLast()] > heights[i]){
                // int index = sta.pollLast();
                int height = heights[sta.pollLast()];
                maxare = Math.max(maxare,height*(i-sta.peekLast()-1));
            }
            sta.addLast(i);
        }

        while(sta.peekLast() != -1){
            int height = heights[sta.pollLast()];
            maxare = Math.max(maxare,height * (heights.length - sta.peekLast()-1));
        }
        return maxare;
    }
}