logo

TechCodeview

Ugotovite, ali je podniz v obliki gore ali ne

Preizkusite na GfG Practice ' title= #practiceLinkDiv { display: none !important; }

Dobili smo niz celih števil in obseg, ki ga moramo ugotoviti, ali ima podniz, ki spada v ta obseg, vrednosti v obliki gore ali ne. Za vse vrednosti podniza pravimo, da so v obliki gore, če bodisi vse vrednosti naraščajo ali padajo bodisi najprej naraščajo in nato padajo. 
Bolj formalno podmatrika [a1 a2 a3…aN] pravimo, da je v obliki gore, če obstaja celo število K 1<= K <= N such that 
a1<= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >= aN  

Primeri:  

  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 stated
Recommended Practice Problem gorske podmatrike Poskusite!

rešitev:  



    Pristop:Težava ima več poizvedb, zato je treba za vsako poizvedbo rešitev izračunati z najmanjšo možno časovno zapletenostjo. Torej ustvarite dva dodatna presledka dolžine prvotne matrike. Za vsak element poiščite zadnji indeks na levi strani, ki narašča, tj. večji od prejšnjega elementa, in poiščite element na desni strani, ki bo shranil prvi indeks na desni strani, ki se zmanjšuje, tj. večji od svojega naslednjega elementa. Če je te vrednosti mogoče izračunati za vsak indeks v konstantnem času, potem je za vsak dani obseg mogoče podati odgovor v konstantnem času.Algoritem: 
    1. Ustvarite dva dodatna prostora dolžine n levo in desno in dodatno spremenljivko lastptr
    2. Inicializiraj levo[0] = 0 in lastptr = 0
    3. Preletite izvirno matriko od drugega indeksa do konca
    4. Za vsak indeks preverite, ali je večji od prejšnjega elementa, če da, nato posodobite lastptr s trenutnim indeksom.
    5. Za vsak indeks shranite lastptr v levo[i]
    6. inicializirati desno [N-1] = N-1 in lastptr = N-1
    7. Preletite izvirno matriko od predzadnjega indeksa do začetka
    8. Za vsak indeks preverite, ali je večji od naslednjega elementa, če da, nato posodobite lastptr s trenutnim indeksom.
    9. Za vsak indeks shranite lastptr v prav[i]
    10. Zdaj obdelajte poizvedbe
    11. za vsako poizvedbo l r če desno[l] >= levo[r] nato natisnite ja drugače št
    Izvedba:
C++ 
// 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 formn';  else  cout << 'Subarray is not in mountain formn';  L = 1;  R = 3;  if (isSubarrayMountainForm(arr left right L R))  cout << 'Subarray is in mountain formn';  else  cout << 'Subarray is not in mountain formn';  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(1N): # 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>
    Izhod: 
Subarray is in mountain form Subarray is not in mountain form
    Analiza kompleksnosti: 
      Časovna zapletenost:O(n). 
      Potrebna sta le dva prehoda, tako da je časovna kompleksnost O(n).Kompleksnost prostora:O(n). 
      Potrebna sta dva dodatna prostora dolžine n, tako da je kompleksnost prostora O(n).


 

Ustvari kviz