Find maximum of minimum for every window size in a given array | An efficient Java program to find maximum of all minimums of windows of different size ; Used to find previous and next smaller ; Arrays to store previous and next smaller ; Initialize elements of left [ ] and right [ ] ; Fill elements of left [ ] using logic discussed on www . geeksforgeeks . org / next - greater - element / https : ; Empty the stack as stack is going to be used for right [ ] ; Fill elements of right [ ] using same logic ; Create and initialize answer array ; Fill answer array by comparing minimums of all lengths computed using left [ ] and right [ ] ; length of the interval ; arr [ i ] is a possible answer for this length ' len ' interval , check if arr [ i ] is more than max for ' len ' ; Some entries in ans [ ] may not be filled yet . Fill them by taking values from right side of ans [ ] ; Print the result ; Driver method
import java . util . Stack ; class Test { static int arr [ ] = { 10 , 20 , 30 , 50 , 10 , 70 , 30 } ; static void printMaxOfMin ( int n ) { Stack < Integer > s = new Stack < > ( ) ; int left [ ] = new int [ n + 1 ] ; int right [ ] = new int [ n + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { left [ i ] = - 1 ; right [ i ] = n ; } for ( int i = 0 ; i < n ; i ++ ) { while ( ! s . empty ( ) && arr [ s . peek ( ) ] >= arr [ i ] ) s . pop ( ) ; if ( ! s . empty ( ) ) left [ i ] = s . peek ( ) ; s . push ( i ) ; } while ( ! s . empty ( ) ) s . pop ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( ! s . empty ( ) && arr [ s . peek ( ) ] >= arr [ i ] ) s . pop ( ) ; if ( ! s . empty ( ) ) right [ i ] = s . peek ( ) ; s . push ( i ) ; } int ans [ ] = new int [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) ans [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int len = right [ i ] - left [ i ] - 1 ; ans [ len ] = Math . max ( ans [ len ] , arr [ i ] ) ; } for ( int i = n - 1 ; i >= 1 ; i -- ) ans [ i ] = Math . max ( ans [ i ] , ans [ i + 1 ] ) ; for ( int i = 1 ; i <= n ; i ++ ) System . out . print ( ans [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { printMaxOfMin ( arr . length ) ; } }