logo

TechCodeview

하위 배열이 산 형태인지 확인

GfG Practice에서 사용해 보세요. ' title= #practiceLinkDiv { 표시: 없음 !중요; }

정수 배열과 이 범위에 속하는 하위 배열이 산 형태의 값을 갖는지 여부를 찾는 데 필요한 범위가 제공됩니다. 모든 값이 증가 또는 감소하거나 먼저 증가한 다음 감소하는 경우 하위 배열의 모든 값은 산 형태라고 합니다. 
더 형식적으로는 하위 배열 [a1 a2 a3…aN] 정수 K 1이 존재하면 산의 형태를 갖는다고 한다.<= K <= N such that 
a1<= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >=aN  

예:  

  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 산 하위 배열 문제 시도해 보세요!

해결책:  



    접근하다:문제에는 쿼리가 여러 개 있으므로 각 쿼리에 대해 가능한 시간 복잡도를 최소화하면서 솔루션을 계산해야 합니다. 따라서 원래 배열 길이만큼 두 개의 추가 공간을 만듭니다. 모든 요소에 대해 증가하는(즉, 이전 요소보다 큰) 왼쪽의 마지막 인덱스를 찾고 오른쪽의 요소를 찾으면 감소하는(즉, 다음 요소보다 큰) 오른쪽의 첫 번째 인덱스가 저장됩니다. 이 값이 모든 인덱스에 대해 일정한 시간 내에 계산될 수 있다면 주어진 모든 범위에 대해 답이 일정한 시간 내에 주어질 수 있습니다.연산: 
    1. 두 개의 추가 공간을 만듭니다. N 왼쪽 그리고 오른쪽 그리고 추가 변수 마지막 ptr
    2. 초기화 왼쪽[0] = 0 및 마지막 ptr = 0
    3. 두 번째 인덱스부터 끝까지 원래 배열을 탐색합니다.
    4. 모든 인덱스에 대해 이전 요소보다 큰지 확인하고 그렇다면 업데이트합니다. 마지막 ptr 현재 인덱스로.
    5. 모든 인덱스 저장소에 대해 마지막 ptr ~에 왼쪽[i]
    6. 초기화 오른쪽[N-1] = N-1 및 마지막 ptr = N-1
    7. 마지막 두 번째 인덱스부터 시작 부분까지 원래 배열을 순회합니다.
    8. 모든 인덱스에 대해 다음 요소보다 큰지 확인하고 그렇다면 업데이트합니다. 마지막 ptr 현재 인덱스로.
    9. 모든 인덱스 저장소에 대해 마지막 ptr ~에 그렇죠[나]
    10. 이제 쿼리를 처리하세요.
    11. 모든 쿼리에 대해 난 r 만약에 오른쪽[l] >= 왼쪽[r] 그런 다음 인쇄 예 또 다른 아니요
    구현:
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>
    산출: 
Subarray is in mountain form Subarray is not in mountain form
    복잡성 분석: 
      시간 복잡도:에). 
      두 번의 순회만 필요하므로 시간 복잡도는 O(n)입니다.공간 복잡도:에). 
      길이가 n인 두 개의 추가 공간이 필요하므로 공간 복잡도는 O(n)입니다.


 

퀴즈 만들기