LargestRectangleInHistogram.java

import java.util.*;
public class LargestRectangleInHistogram {
    public static int maxArea(int arr[]){
        int arr1[]=new int[arr.length];
        Stack<Integer> s = new Stack<>();
        int nsr[]=new int[arr.length];
        int nsl[]=new int[arr.length];
        for(int i=arr.length-1;i>=0;i--){
            while(!s.isEmpty()&&arr[s.peek()]>=arr[i]){
                s.pop();
            }
            if(s.isEmpty()){
                nsr[i]=arr.length;
            }else{
                nsr[i]=s.peek();
            }
            s.push(i);
        }
        s.clear();
        for(int i=0;i<arr.length;i++){
            while(!s.isEmpty()&&arr[s.peek()]>=arr[i]){
                s.pop();
            }
            if (s.isEmpty()){
                nsl[i]=-1;
            }else{
                nsl[i]=s.peek();
            }
            s.push(i);
        }
        int max=0;
        for(int i=0;i<arr.length;i++){
            int width=nsr[i]-nsl[i]-1;
            int area=arr[i]*width;
            max=Math.max(max,area);
        }
        return max;
    }
    public static void main(String[] args) {
        int arr[]={2,1,5,6,2,3};
        System.out.println(maxArea(arr));
    }
}