Trova il successivo Minore del successivo Maggiore in un array
Dato un array di numeri interi, trova il successivo più piccolo Di elemento successivo più grande di ogni elemento dell'array.
Nota : Elementi per i quali non esiste un elemento maggiore o non esiste un elemento minore o maggiore print -1.
Esempi:
Input : arr[] = {5 1 9 2 5 1 7} Output: 2 2 -1 1 -1 -1 -1 Explanation : Next Greater -> Right Smaller 5 -> 9 9 -> 2 1 -> 9 9 -> 2 9 -> -1 -1 -> -1 2 -> 5 5 -> 1 5 -> 7 7 -> -1 1 -> 7 7 -> -1 7 -> -1 -1 -> -1 Input : arr[] = {4 8 2 1 9 5 6 3} Output : 2 5 5 5 -1 3 -1 -1 UN soluzione semplice è scorrere tutti gli elementi. Per ogni elemento trova l'elemento successivo più grande dell'elemento corrente e poi trova l'elemento più piccolo a destra per l'elemento successivo più grande corrente.
Codice-
C++ // C++ Program to find Right smaller element of next // greater element #include using namespace std ; // Function to find Right smaller element of next greater // element void nextSmallerOfNextGreater ( int arr [] int n ) { vector < int > vec ; //For 1st n-1 elements of vector for ( int i = 0 ; i < n -1 ; i ++ ){ int temp = arr [ i ]; int next = -1 ; int ans = -1 ; for ( int j = i + 1 ; j < n ; j ++ ){ if ( arr [ j ] > temp ){ next = j ; break ; } } if ( next == -1 ){ vec . push_back ( -1 );} else { for ( int j = next + 1 ; j < n ; j ++ ){ if ( arr [ j ] < arr [ next ]){ ans = j ; break ; } } if ( ans == -1 ){ vec . push_back ( -1 );} else { vec . push_back ( arr [ ans ]);} } } vec . push_back ( -1 ); //For last element of vector for ( auto x : vec ){ cout < < x < < ' ' ; } cout < < endl ; } // Driver program int main () { int arr [] = { 5 1 9 2 5 1 7 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); nextSmallerOfNextGreater ( arr n ); return 0 ; }
Java // Java Program to find Right smaller element of next // greater element import java.util.* ; public class Main { // Function to find Right smaller element of next greater element static void nextSmallerOfNextGreater ( int arr [] int n ) { ArrayList < Integer > vec = new ArrayList < Integer > (); // For 1st n-1 elements of vector for ( int i = 0 ; i < n - 1 ; i ++ ) { int temp = arr [ i ] ; int next = - 1 ; int ans = - 1 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > temp ) { next = j ; break ; } } if ( next == - 1 ) { vec . add ( - 1 ); } else { for ( int j = next + 1 ; j < n ; j ++ ) { if ( arr [ j ] < arr [ next ] ) { ans = j ; break ; } } if ( ans == - 1 ) { vec . add ( - 1 ); } else { vec . add ( arr [ ans ] ); } } } vec . add ( - 1 ); // For last element of vector for ( int x : vec ) { System . out . print ( x + ' ' ); } System . out . println (); } // Driver program public static void main ( String [] args ) { int arr [] = { 5 1 9 2 5 1 7 }; int n = arr . length ; nextSmallerOfNextGreater ( arr n ); } }
Python3 # Function to find Right smaller element of next greater element def nextSmallerOfNextGreater ( arr n ): vec = [] # For 1st n-1 elements of vector for i in range ( n - 1 ): temp = arr [ i ] next = - 1 ans = - 1 for j in range ( i + 1 n ): if arr [ j ] > temp : next = j break if next == - 1 : vec . append ( - 1 ) else : for j in range ( next + 1 n ): if arr [ j ] < arr [ next ]: ans = j break if ans == - 1 : vec . append ( - 1 ) else : vec . append ( arr [ ans ]) vec . append ( - 1 ) # For last element of vector for x in vec : print ( x end = ' ' ) print () # Driver program arr = [ 5 1 9 2 5 1 7 ] n = len ( arr ) nextSmallerOfNextGreater ( arr n )
C# using System ; using System.Collections.Generic ; public class MainClass { // Function to find Right smaller element of next // greater element static void nextSmallerOfNextGreater ( int [] arr int n ) { List < int > vec = new List < int > (); // For 1st n-1 elements of vector for ( int i = 0 ; i < n - 1 ; i ++ ) { int temp = arr [ i ]; int next = - 1 ; int ans = - 1 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > temp ) { next = j ; break ; } } if ( next == - 1 ) { vec . Add ( - 1 ); } else { for ( int j = next + 1 ; j < n ; j ++ ) { if ( arr [ j ] < arr [ next ]) { ans = j ; break ; } } if ( ans == - 1 ) { vec . Add ( - 1 ); } else { vec . Add ( arr [ ans ]); } } } vec . Add ( - 1 ); // For last element of vector foreach ( var x in vec ) { Console . Write ( x + ' ' ); } Console . WriteLine (); } // Driver program public static void Main () { int [] arr = { 5 1 9 2 5 1 7 }; int n = arr . Length ; nextSmallerOfNextGreater ( arr n ); } }
JavaScript // Function to find Right smaller element of next greater element function nextSmallerOfNextGreater ( arr n ) { let vec = []; // For 1st n-1 elements of vector for ( let i = 0 ; i < n - 1 ; i ++ ) { let temp = arr [ i ]; let next = - 1 ; let ans = - 1 ; for ( let j = i + 1 ; j < n ; j ++ ) { if ( arr [ j ] > temp ) { next = j ; break ; } } if ( next == - 1 ) { vec . push ( - 1 ); } else { for ( let j = next + 1 ; j < n ; j ++ ) { if ( arr [ j ] < arr [ next ]) { ans = j ; break ; } } if ( ans == - 1 ) { vec . push ( - 1 ); } else { vec . push ( arr [ ans ]); } } } vec . push ( - 1 ); // For last element of vector for ( let x of vec ) { process . stdout . write ( x + ' ' ); } console . log (); } // Driver program let arr = [ 5 1 9 2 5 1 7 ]; let n = arr . length ; nextSmallerOfNextGreater ( arr n );
Produzione
2 2 -1 1 -1 -1 -1
Complessità temporale di questa soluzione è O(n 2 ).
Complessità spaziale: O(1)
UN soluzione efficiente impiega tempo O(n). Si noti che è la combinazione di Elemento successivo più grande & successivo elemento più piccolo nella matrice.
Let input array be 'arr[]' and size of array be 'n' find next greatest element of every element step 1 : Create an empty stack (S) in which we store the indexes and NG[] that is user to store the indexes of NGE of every element. step 2 : Traverse the array in reverse order where i goes from (n-1 to 0) a) While S is non empty and the top element of S is smaller than or equal to 'arr[i]': pop S b) If S is empty arr[i] has no greater element NG[i] = -1 c) else we have next greater element NG[i] = S.top() // here we store the index of NGE d) push current element index in stack S.push(i) Find Right smaller element of every element step 3 : create an array RS[] used to store the index of right smallest element step 4 : we repeat step (1 & 2) with little bit of modification in step 1 & 2 . they are : a). we use RS[] in place of NG[]. b). In step (2.a) we pop element form stack S while S is not empty or the top element of S is greater than or equal to 'arr[i]' step 5 : compute all RSE of NGE : where i goes from 0 to n-1 if NG[ i ] != -1 && RS[ NG [ i]] ! =-1 print arr[RS[NG[i]]] else print -1
Di seguito è riportata l'implementazione dell'idea di cui sopra
C++ // C++ Program to find Right smaller element of next // greater element #include using namespace std ; // function find Next greater element void nextGreater ( int arr [] int n int next [] char order ) { // create empty stack stack < int > S ; // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for ( int i = n -1 ; i >= 0 ; i -- ) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while ( ! S . empty () && (( order == 'G' ) ? arr [ S . top ()] <= arr [ i ] : arr [ S . top ()] >= arr [ i ])) S . pop (); // store the next greater element of current element if ( ! S . empty ()) next [ i ] = S . top (); // If all elements in S were smaller than arr[i] else next [ i ] = -1 ; // Push this element S . push ( i ); } } // Function to find Right smaller element of next greater // element void nextSmallerOfNextGreater ( int arr [] int n ) { int NG [ n ]; // stores indexes of next greater elements int RS [ n ]; // stores indexes of right smaller elements // Find next greater element // Here G indicate next greater element nextGreater ( arr n NG 'G' ); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater ( arr n RS 'S' ); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for ( int i = 0 ; i < n ; i ++ ) { if ( NG [ i ] != -1 && RS [ NG [ i ]] != -1 ) cout < < arr [ RS [ NG [ i ]]] < < ' ' ; else cout < < '-1' < < ' ' ; } } // Driver program int main () { int arr [] = { 5 1 9 2 5 1 7 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); nextSmallerOfNextGreater ( arr n ); return 0 ; }
Java // Java Program to find Right smaller element of next // greater element import java.util.Stack ; public class Main { // function find Next greater element public static void nextGreater ( int arr [] int next [] char order ) { // create empty stack Stack < Integer > stack = new Stack <> (); // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for ( int i = arr . length - 1 ; i >= 0 ; i -- ) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while ( ! stack . isEmpty () && (( order == 'G' ) ? arr [ stack . peek () ] <= arr [ i ] : arr [ stack . peek () ] >= arr [ i ] )) stack . pop (); // store the next greater element of current element if ( ! stack . isEmpty ()) next [ i ] = stack . peek (); // If all elements in S were smaller than arr[i] else next [ i ] = - 1 ; // Push this element stack . push ( i ); } } // Function to find Right smaller element of next greater // element public static void nextSmallerOfNextGreater ( int arr [] ) { int NG []= new int [ arr . length ] ; // stores indexes of next greater elements int RS []= new int [ arr . length ] ; // stores indexes of right smaller elements // Find next greater element // Here G indicate next greater element nextGreater ( arr NG 'G' ); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater ( arr RS 'S' ); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for ( int i = 0 ; i < arr . length ; i ++ ) { if ( NG [ i ] != - 1 && RS [ NG [ i ]] != - 1 ) System . out . print ( arr [ RS [ NG [ i ]]]+ ' ' ); else System . out . print ( '-1 ' ); } } public static void main ( String args [] ) { int arr [] = { 5 1 9 2 5 1 7 }; nextSmallerOfNextGreater ( arr ); } } //This code is contributed by Gaurav Tiwari
Python 3 # Python 3 Program to find Right smaller element of next # greater element # function find Next greater element def nextGreater ( arr n next order ): S = [] # Traverse all array elements in reverse order # order == 'G' we compute next greater elements of # every element # order == 'S' we compute right smaller element of # every element for i in range ( n - 1 - 1 - 1 ): # Keep removing top element from S while the top # element is smaller than or equal to arr[i] (if Key is G) # element is greater than or equal to arr[i] (if order is S) while ( S != [] and ( arr [ S [ len ( S ) - 1 ]] <= arr [ i ] if ( order == 'G' ) else arr [ S [ len ( S ) - 1 ]] >= arr [ i ] )): S . pop () # store the next greater element of current element if ( S != []): next [ i ] = S [ len ( S ) - 1 ] # If all elements in S were smaller than arr[i] else : next [ i ] = - 1 # Push this element S . append ( i ) # Function to find Right smaller element of next greater # element def nextSmallerOfNextGreater ( arr n ): NG = [ None ] * n # stores indexes of next greater elements RS = [ None ] * n # stores indexes of right smaller elements # Find next greater element # Here G indicate next greater element nextGreater ( arr n NG 'G' ) # Find right smaller element # using same function nextGreater() # Here S indicate right smaller elements nextGreater ( arr n RS 'S' ) # If NG[i] == -1 then there is no smaller element # on right side. We can find Right smaller of next # greater by arr[RS[NG[i]]] for i in range ( n ): if ( NG [ i ] != - 1 and RS [ NG [ i ]] != - 1 ): print ( arr [ RS [ NG [ i ]]] end = ' ' ) else : print ( '-1' end = ' ' ) # Driver program if __name__ == '__main__' : arr = [ 5 1 9 2 5 1 7 ] n = len ( arr ) nextSmallerOfNextGreater ( arr n ) # this code is contributed by ChitraNayal
C# using System ; using System.Collections.Generic ; // C# Program to find Right smaller element of next // greater element public class GFG { // function find Next greater element public static void nextGreater ( int [] arr int [] next char order ) { // create empty stack Stack < int > stack = new Stack < int > (); // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for ( int i = arr . Length - 1 ; i >= 0 ; i -- ) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while ( stack . Count != 0 && (( order == 'G' ) ? arr [ stack . Peek ()] <= arr [ i ]: arr [ stack . Peek ()] >= arr [ i ])) stack . Pop (); // store the next greater element of current element if ( stack . Count != 0 ) next [ i ] = stack . Peek (); // If all elements in S were smaller than arr[i] else next [ i ] = - 1 ; // Push this element stack . Push ( i ); } } // Function to find Right smaller element of next greater // element public static void nextSmallerOfNextGreater ( int [] arr ) { int [] NG = new int [ arr . Length ]; // stores indexes of next greater elements int [] RS = new int [ arr . Length ]; // stores indexes of right smaller elements // Find next greater element // Here G indicate next greater element nextGreater ( arr NG 'G' ); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater ( arr RS 'S' ); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for ( int i = 0 ; i < arr . Length ; i ++ ) { if ( NG [ i ] != - 1 && RS [ NG [ i ]] != - 1 ) Console . Write ( arr [ RS [ NG [ i ]]] + ' ' ); else Console . Write ( '-1 ' ); } } public static void Main () { int [] arr = { 5 1 9 2 5 1 7 }; nextSmallerOfNextGreater ( arr ); } } // This code is contributed by PrinciRaj1992
JavaScript < script > // Javascript Program to find Right smaller element of next // greater element // function find Next greater element function nextGreater ( arr next order ) { // create empty stack let stack = []; // Traverse all array elements in reverse order // order == 'G' we compute next greater elements of // every element // order == 'S' we compute right smaller element of // every element for ( let i = arr . length - 1 ; i >= 0 ; i -- ) { // Keep removing top element from S while the top // element is smaller than or equal to arr[i] (if Key is G) // element is greater than or equal to arr[i] (if order is S) while ( stack . length != 0 && (( order == 'G' ) ? arr [ stack [ stack . length - 1 ]] <= arr [ i ] : arr [ stack [ stack . length - 1 ]] >= arr [ i ])) stack . pop (); // store the next greater element of current element if ( stack . length != 0 ) next [ i ] = stack [ stack . length - 1 ]; // If all elements in S were smaller than arr[i] else next [ i ] = - 1 ; // Push this element stack . push ( i ); } } // Function to find Right smaller element of next greater // element function nextSmallerOfNextGreater ( arr ) { let NG = new Array ( arr . length ); // stores indexes of next greater elements let RS = new Array ( arr . length ); // stores indexes of right smaller elements for ( let i = 0 ; i < arr . length ; i ++ ) { NG [ i ] = 0 ; RS [ i ] = 0 ; } // Find next greater element // Here G indicate next greater element nextGreater ( arr NG 'G' ); // Find right smaller element // using same function nextGreater() // Here S indicate right smaller elements nextGreater ( arr RS 'S' ); // If NG[i] == -1 then there is no smaller element // on right side. We can find Right smaller of next // greater by arr[RS[NG[i]]] for ( let i = 0 ; i < arr . length ; i ++ ) { if ( NG [ i ] != - 1 && RS [ NG [ i ]] != - 1 ) document . write ( arr [ RS [ NG [ i ]]] + ' ' ); else document . write ( '-1 ' ); } } // Driver code let arr = [ 5 1 9 2 5 1 7 ]; nextSmallerOfNextGreater ( arr ); // This code is contributed by rag2127 < /script>
Produzione
2 2 -1 1 -1 -1 -1
Complessità temporale: SU) dove n è la dimensione dell'array specificato.
Spazio ausiliario: O(n ) dove n è la dimensione dell'array specificato.
Crea quiz
