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); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter