Area of histogram

PHOTO EMBED

Mon Dec 19 2022 17:33:25 GMT+0000 (Coordinated Universal Time)

Saved by @Beluga #java #stacks

import java.util.Stack;

public class HistogramArea {
   /* public static int minVal(int[] arr, int i,int j){
        int min= Integer.MAX_VALUE;
        for(int k=i;k<=j;k++){
            min=Math.min(min,arr[k]);
        }
        return min;
    }
    public static int maxArea(@NotNull int[] arr){
        int max=Integer.MIN_VALUE, area=0;
        for(int i=0;i< arr.length;i++){
            for (int j = i; j < arr.length; j++) {
                int width=j-i+1;
                int length=minVal(arr,i,j);
                area=length*width;
                max=Math.max(area,max);
            }
        }
        return max;
    }*/
    public static void maxArea(int[] arr){
        int maxArea=0;
        int[] nsr =new int[arr.length];
        int[] nsl =new int[arr.length];
        Stack<Integer> s=new Stack<>();
        //next smaller right
        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=new Stack<>();
        //next smaller left
        for (int i = 0;i<arr.length;i++) {
            while(!s.isEmpty()&&arr[s.peek()]>=arr[i]){
                s.pop();
            }
            if(s.isEmpty()) nsl[i]=arr.length;
            else nsl[i]=s.peek();
            s.push(i);
        }

        for (int i = 0; i < arr.length; i++) {
            int h=arr[i];
            int w=nsr[i]-nsl[i]-1;
            int area=h*w;
            maxArea=Math.max(area,maxArea);
        }
        System.out.println(maxArea);
    }

    public static void main(String[] args){
        int[] arr={2,1,5,6,2,3};
        maxArea(arr);
    }
}
content_copyCOPY