Határozza meg, hogy az alrendszer hegy alakú-e vagy sem
Próbáld ki a GfG Practice-n 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Adunk egy egész számok tömbjét és egy tartományt, amelyre meg kell találnunk, hogy az ebbe a tartományba eső résztömbnek vannak-e hegy formájú értékei vagy sem. Az alrendszer minden értékét hegy formájúnak nevezzük, ha minden érték növekszik vagy csökken, vagy először nő, majd csökken.
Formálisabban egy alrendszer [a1 a2 a3…aN] hegy formájúnak mondjuk, ha létezik K 1 egész szám <= K <= N such that
a1 <= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >= aN
Példák:
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 Mountain Subarray probléma Próbáld ki!
Megoldás:
- Hozzon létre két extra hosszúságú mezőt n balra és jobbra és egy extra változó lastptr
- Inicializálás balra[0] = 0 és lastptr = 0
- Haladjon át az eredeti tömbön a második indextől a végéig
- Minden indexnél ellenőrizze, hogy nagyobb-e az előző elemnél, ha igen, akkor frissítse a lastptr az aktuális indexszel.
- Minden indextárhoz a lastptr be balra [i]
- inicializálni jobb[N-1] = N-1 és lastptr = N-1
- Haladjon át az eredeti tömbön a második utolsó indextől az elejéig
- Minden indexnél ellenőrizze, hogy nagyobb-e, mint a következő elem, ha igen, akkor frissítse a lastptr az aktuális indexszel.
- Minden indextárhoz a lastptr be helyes[i]
- Most dolgozza fel a lekérdezéseket
- minden lekérdezéshez l r ha jobb[l] >= bal[r] majd nyomtasd ki igen más nem
// 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
Csak két bejárásra van szükség, így az időbonyolultság O(n).
Két extra n hosszúságú térre van szükség, így a tér összetettsége O(n).
Lehet, Hogy Tetszeni Fog
Top Cikkek
