84. Largest Rectangle in Histogr

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer>st=new Stack<Integer>();
        int res = 0;
        int[]a = new int[height.length+1];
        for(int i=0;i<height.length;i++)a[i]=height[i];
        a[height.length]=0;
        
        for(int i=0; i<a.length; i++) {
            while(!st.isEmpty() && a[st.peek()]>=a[i]) {
                int idx = st.pop();
                int width = i-(st.isEmpty()?-1:st.peek())-1;
                res = Math.max(res, a[idx]*width);
            }
            st.add(i);
        }
        
        return res;
    }
    
    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(s.largestRectangleArea(new int[]{1}));
    }
}