84. Largest Rectangle in Histogram

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<>();
        int res = 0;
        for(int i=0; i<heights.length; i++){
            while(!st.isEmpty() && heights[st.peek()] >= heights[i]){
                int top = st.pop();
                int pse = st.isEmpty()?-1:st.peek();
                res = Math.max(res, heights[top]*(i-pse-1));
            }
            st.push(i);
        }
        while(!st.isEmpty()){
            int top = st.pop();
            int nse=heights.length, pse = st.isEmpty()?-1:st.peek();
            res = Math.max(res, heights[top]*(nse-pse-1));
        }
        return res;
    }
}