查找子數組是否為山脈形式 · GeeksForGeeks 中文系列教程

# 查找子數組是否為山脈形式 > 原文： [https://www.geeksforgeeks.org/find-whether-subarray-form-mountain-not/](https://www.geeksforgeeks.org/find-whether-subarray-form-mountain-not/) 給定一個整數數組和一個范圍，我們需要查找落入該范圍的子數組是否具有山峰形式的值。如果所有值都是遞增或遞減的，或者先遞增然后遞減的，則子數組的所有值都稱為山的形式。更正式地講，如果存在整數 K，則稱子數組 *[a1，a2，a3…aN]* 為山的形式，因此< = K < = N *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 ``` **解決方案：** * **方法**：該問題有多個查詢，因此對于每個查詢，應以盡可能少的時間復雜性來計算解決方案。因此，請為原始數組增加兩個額外的空格。對于每個元素，找到左側的最后一個索引，該索引增加（即大于前一個元素），找到右側的元素，將在右側存儲第一個索引，該索引遞減（即大于其下一個元素）。如果可以在恒定時間內為每個索引計算這些值，那么對于每個給定范圍，可以在恒定時間內給出答案。 * **算法**： 1. 創建兩個長度為 *n* ，*左*和*右*的額外空間，以及一個額外的變量 *lastptr* 2. 初始化*左[0]* = 0 和 *lastptr* = 0 3. 從第二個索引到末尾遍歷原始數組 4. 對于每個索引，檢查它是否大于上一個元素，如果是，則使用當前索引更新 *lastptr* 。 5. 對于每個索引，將 *lastptr* 存儲在*左[i]* 中 6. 初始化*右[N-1]* = N-1 和 *lastptr* = N-1 7. 從倒數第二個索引到起始位置遍歷原始數組 8. 對于每個索引，檢查它是否大于下一個元素，如果是，則使用當前索引更新 *lastptr* 。 9. 對于每個索引，將 *lastptr* 存儲在*中[i]* 10. 現在處理查詢 11. 對于每個查詢 *l，r* ，如果 *right [l] > = left [r]* ，則打印*是*否則*否* * **實現**： ## C/C++ ``` // C++ program to check whether a subarray is in // mountain form or not #include <bits/stdc++.h> 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 ``` * **輸出**： ``` Subarray is in mountain form Subarray is not in mountain form ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。僅需要兩個遍歷，因此時間復雜度為`O(n)`。 * **空間復雜度**：`O(n)`。需要兩個長度為 n 的額外空間，因此空間復雜度為`O(n)`。本文由 [**Utkarsh Trivedi**](https://in.linkedin.com/in/utkarsh-trivedi-253069a7) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，您還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。