查找子数组是否为山脉形式 · 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。