Find maximum of minimum for every window size in a given array | An efficient Python3 program to find maximum of all minimums of windows of different sizes ; Used to find 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 Code
def printMaxOfMin ( arr , n ) : NEW_LINE INDENT s = [ ] NEW_LINE left = [ - 1 ] * ( n + 1 ) NEW_LINE right = [ n ] * ( n + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT while ( len ( s ) != 0 and arr [ s [ - 1 ] ] >= arr [ i ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT if ( len ( s ) != 0 ) : NEW_LINE INDENT left [ i ] = s [ - 1 ] NEW_LINE DEDENT s . append ( i ) NEW_LINE DEDENT while ( len ( s ) != 0 ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT while ( len ( s ) != 0 and arr [ s [ - 1 ] ] >= arr [ i ] ) : NEW_LINE INDENT s . pop ( ) NEW_LINE DEDENT if ( len ( s ) != 0 ) : NEW_LINE INDENT right [ i ] = s [ - 1 ] NEW_LINE DEDENT s . append ( i ) NEW_LINE DEDENT ans = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT ans [ i ] = 0 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT Len = right [ i ] - left [ i ] - 1 NEW_LINE ans [ Len ] = max ( ans [ Len ] , arr [ i ] ) NEW_LINE DEDENT for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT ans [ i ] = max ( ans [ i ] , ans [ i + 1 ] ) NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 10 , 20 , 30 , 50 , 10 , 70 , 30 ] NEW_LINE n = len ( arr ) NEW_LINE printMaxOfMin ( arr , n ) NEW_LINE DEDENT