Zistite, či má podpolie tvar hory alebo nie
Vyskúšajte to na GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Dostali sme pole celých čísel a rozsah, ktorý potrebujeme, aby sme zistili, či podpole, ktoré spadá do tohto rozsahu, má hodnoty vo forme hora alebo nie. Všetky hodnoty podpola sú označené ako hora, ak buď všetky hodnoty rastú alebo klesajú, alebo najprv rastú a potom klesajú.
Formálnejšie subarray [a1 a2 a3…aN] hovorí sa, že má tvar hory, ak existuje celé číslo K 1 <= K <= N such that
a1 <= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >= aN
Príklady:
Input : Arr[] = [2 3 2 4 4 6 3 2] Range = [0 2] Output : Yes Explanation: The output is yes subarray is [2 3 2] so subarray first increases and then decreases Input: Arr[] = [2 3 2 4 4 6 3 2] Range = [2 7] Output: Yes Explanation: The output is yes subarray is [2 4 4 6 3 2] so subarray first increases and then decreases Input: Arr[]= [2 3 2 4 4 6 3 2] Range = [1 3] Output: no Explanation: The output is no subarray is [3 2 4] so subarray is not in the form above statedRecommended Practice Problém horskej subarray Skúste to!
Riešenie:
- Vytvorte dve ďalšie medzery dĺžky n vľavo a správne a dodatočná premenná lastptr
- Inicializovať vľavo[0] = 0 a lastptr = 0
- Prejdite pôvodné pole od druhého indexu po koniec
- Pre každý index skontrolujte, či je väčší ako predchádzajúci prvok, ak áno, potom aktualizujte lastptr s aktuálnym indexom.
- Pre každý indexový ukladací priestor lastptr v vľavo[i]
- inicializovať vpravo[N-1] = N-1 a lastptr = N-1
- Prejdite pôvodné pole od predposledného indexu po začiatok
- Pre každý index skontrolujte, či je väčší ako nasledujúci prvok, ak áno, potom aktualizujte lastptr s aktuálnym indexom.
- Pre každý indexový ukladací priestor lastptr v vpravo[i]
- Teraz spracujte otázky
- pre každý dotaz l r ak vpravo[l] >= vľavo[r] potom vytlačte áno inak č
// C++ program to check whether a subarray is in // mountain form or not #include using namespace std ; // Utility method to construct left and right array int preprocess ( int arr [] int N int left [] int right []) { // Initialize first left index as that index only left [ 0 ] = 0 ; int lastIncr = 0 ; for ( int i = 1 ; i < N ; i ++ ) { // if current value is greater than previous // update last increasing if ( arr [ i ] > arr [ i - 1 ]) lastIncr = i ; left [ i ] = lastIncr ; } // Initialize last right index as that index only right [ N - 1 ] = N - 1 ; int firstDecr = N - 1 ; for ( int i = N - 2 ; i >= 0 ; i -- ) { // if current value is greater than next // update first decreasing if ( arr [ i ] > arr [ i + 1 ]) firstDecr = i ; right [ i ] = firstDecr ; } } // Method returns true if arr[L..R] is in mountain form bool isSubarrayMountainForm ( int arr [] int left [] int right [] int L int R ) { // return true only if right at starting range is // greater than left at ending range return ( right [ L ] >= left [ R ]); } // Driver code to test above methods int main () { int arr [] = { 2 3 2 4 4 6 3 2 }; int N = sizeof ( arr ) / sizeof ( int ); int left [ N ] right [ N ]; preprocess ( arr N left right ); int L = 0 ; int R = 2 ; if ( isSubarrayMountainForm ( arr left right L R )) cout < < 'Subarray is in mountain form n ' ; else cout < < 'Subarray is not in mountain form n ' ; L = 1 ; R = 3 ; if ( isSubarrayMountainForm ( arr left right L R )) cout < < 'Subarray is in mountain form n ' ; else cout < < 'Subarray is not in mountain form n ' ; return 0 ; }
Java // Java program to check whether a subarray is in // mountain form or not class SubArray { // Utility method to construct left and right array static void preprocess ( int arr [] int N int left [] int right [] ) { // initialize first left index as that index only left [ 0 ] = 0 ; int lastIncr = 0 ; for ( int i = 1 ; i < N ; i ++ ) { // if current value is greater than previous // update last increasing if ( arr [ i ] > arr [ i - 1 ] ) lastIncr = i ; left [ i ] = lastIncr ; } // initialize last right index as that index only right [ N - 1 ] = N - 1 ; int firstDecr = N - 1 ; for ( int i = N - 2 ; i >= 0 ; i -- ) { // if current value is greater than next // update first decreasing if ( arr [ i ] > arr [ i + 1 ] ) firstDecr = i ; right [ i ] = firstDecr ; } } // method returns true if arr[L..R] is in mountain form static boolean isSubarrayMountainForm ( int arr [] int left [] int right [] int L int R ) { // return true only if right at starting range is // greater than left at ending range return ( right [ L ] >= left [ R ] ); } public static void main ( String [] args ) { int arr [] = { 2 3 2 4 4 6 3 2 }; int N = arr . length ; int left [] = new int [ N ] ; int right [] = new int [ N ] ; preprocess ( arr N left right ); int L = 0 ; int R = 2 ; if ( isSubarrayMountainForm ( arr left right L R )) System . out . println ( 'Subarray is in mountain form' ); else System . out . println ( 'Subarray is not in mountain form' ); L = 1 ; R = 3 ; if ( isSubarrayMountainForm ( arr left right L R )) System . out . println ( 'Subarray is in mountain form' ); else System . out . println ( 'Subarray is not in mountain form' ); } } // This Code is Contributed by Saket Kumar
Python3 # Python 3 program to check whether a subarray is in # mountain form or not # Utility method to construct left and right array def preprocess ( arr N left right ): # initialize first left index as that index only left [ 0 ] = 0 lastIncr = 0 for i in range ( 1 N ): # if current value is greater than previous # update last increasing if ( arr [ i ] > arr [ i - 1 ]): lastIncr = i left [ i ] = lastIncr # initialize last right index as that index only right [ N - 1 ] = N - 1 firstDecr = N - 1 i = N - 2 while ( i >= 0 ): # if current value is greater than next # update first decreasing if ( arr [ i ] > arr [ i + 1 ]): firstDecr = i right [ i ] = firstDecr i -= 1 # method returns true if arr[L..R] is in mountain form def isSubarrayMountainForm ( arr left right L R ): # return true only if right at starting range is # greater than left at ending range return ( right [ L ] >= left [ R ]) # Driver code if __name__ == '__main__' : arr = [ 2 3 2 4 4 6 3 2 ] N = len ( arr ) left = [ 0 for i in range ( N )] right = [ 0 for i in range ( N )] preprocess ( arr N left right ) L = 0 R = 2 if ( isSubarrayMountainForm ( arr left right L R )): print ( 'Subarray is in mountain form' ) else : print ( 'Subarray is not in mountain form' ) L = 1 R = 3 if ( isSubarrayMountainForm ( arr left right L R )): print ( 'Subarray is in mountain form' ) else : print ( 'Subarray is not in mountain form' ) # This code is contributed by # Surendra_Gangwar
C# // C# program to check whether // a subarray is in mountain // form or not using System ; class GFG { // Utility method to construct // left and right array static void preprocess ( int [] arr int N int [] left int [] right ) { // initialize first left // index as that index only left [ 0 ] = 0 ; int lastIncr = 0 ; for ( int i = 1 ; i < N ; i ++ ) { // if current value is // greater than previous // update last increasing if ( arr [ i ] > arr [ i - 1 ]) lastIncr = i ; left [ i ] = lastIncr ; } // initialize last right // index as that index only right [ N - 1 ] = N - 1 ; int firstDecr = N - 1 ; for ( int i = N - 2 ; i >= 0 ; i -- ) { // if current value is // greater than next // update first decreasing if ( arr [ i ] > arr [ i + 1 ]) firstDecr = i ; right [ i ] = firstDecr ; } } // method returns true if // arr[L..R] is in mountain form static bool isSubarrayMountainForm ( int [] arr int [] left int [] right int L int R ) { // return true only if right at // starting range is greater // than left at ending range return ( right [ L ] >= left [ R ]); } // Driver Code static public void Main () { int [] arr = { 2 3 2 4 4 6 3 2 }; int N = arr . Length ; int [] left = new int [ N ]; int [] right = new int [ N ]; preprocess ( arr N left right ); int L = 0 ; int R = 2 ; if ( isSubarrayMountainForm ( arr left right L R )) Console . WriteLine ( 'Subarray is in ' + 'mountain form' ); else Console . WriteLine ( 'Subarray is not ' + 'in mountain form' ); L = 1 ; R = 3 ; if ( isSubarrayMountainForm ( arr left right L R )) Console . WriteLine ( 'Subarray is in ' + 'mountain form' ); else Console . WriteLine ( 'Subarray is not ' + 'in mountain form' ); } } // This code is contributed by aj_36
JavaScript < script > // Javascript program to check whether // a subarray is in mountain // form or not // Utility method to construct // left and right array function preprocess ( arr N left right ) { // initialize first left // index as that index only left [ 0 ] = 0 ; let lastIncr = 0 ; for ( let i = 1 ; i < N ; i ++ ) { // if current value is // greater than previous // update last increasing if ( arr [ i ] > arr [ i - 1 ]) lastIncr = i ; left [ i ] = lastIncr ; } // initialize last right // index as that index only right [ N - 1 ] = N - 1 ; let firstDecr = N - 1 ; for ( let i = N - 2 ; i >= 0 ; i -- ) { // if current value is // greater than next // update first decreasing if ( arr [ i ] > arr [ i + 1 ]) firstDecr = i ; right [ i ] = firstDecr ; } } // method returns true if // arr[L..R] is in mountain form function isSubarrayMountainForm ( arr left right L R ) { // return true only if right at // starting range is greater // than left at ending range return ( right [ L ] >= left [ R ]); } let arr = [ 2 3 2 4 4 6 3 2 ]; let N = arr . length ; let left = new Array ( N ); let right = new Array ( N ); preprocess ( arr N left right ); let L = 0 ; let R = 2 ; if ( isSubarrayMountainForm ( arr left right L R )) document . write ( 'Subarray is in ' + 'mountain form' + ' ' ); else document . write ( 'Subarray is not ' + 'in mountain form' + ' ' ); L = 1 ; R = 3 ; if ( isSubarrayMountainForm ( arr left right L R )) document . write ( 'Subarray is in ' + 'mountain form' ); else document . write ( 'Subarray is not ' + 'in mountain form' ); < /script>
Subarray is in mountain form Subarray is not in mountain form
Potrebné sú len dva prechody, takže časová zložitosť je O(n).
Potrebné sú dva ďalšie priestory dĺžky n, takže priestorová zložitosť je O(n).
Mohlo By Sa Vám Páčiť
Najlepšie Články
