C++ 中查找最长湍流子数组

2025年5月15日 | 阅读 7 分钟

在挑战的领域中，寻找子数组的任务呈现了一个引人入胜的难题。湍流子数组由相邻元素在递增和递减顺序之间交替的特征来识别。成功应对此任务需要理解数组操作和模式识别。本文深入探讨了 C++ 中子数组的概念，讨论了问题陈述和一种可能的实现。

问题描述

在此问题陈述中，主要目标是识别给定数组中遵循湍流准则的子集。如果子数组的元素在递增和严格递减值之间振荡，则认为该子数组是湍流的。

为了定义子数组，考虑 arr[i] arr[i+1]... arr[j]，其中；

对于任何 i <= k < j，当 k 为偶数时，arr[k] < arr[k+1] 成立。

对于任何 i <= k < j，当 k 为奇数时，arr[k] > arr[k+1] 成立。

目标是确定给定数组中子数组的大小。

示例；

给定数组 arr = [1, 5, 3, 7, 4, 6, 9, 2, 8]

在此数组中，交替序列为 '[1, 5, 3, 7, 4, 6, 9]'，长度为 7。

让我们确保此序列遵循交替模式规则；

“1 比 5”（在索引 0 处向上）
“5 比 3”（在索引 1 处向下）
“3 比 7”（在索引 2 处向上）
“7 比 4”（在索引 3 处向下）
“4 比 6”（在索引 4 处向上）
“6 比 9”（在索引 5 处向上）

此时，由于下一个数字“2”小于“9”，因此模式发生了变化。此外，索引 6 是一个值。因此，最长的湍流子数组由 '[1, 5, 3, 7 4 6 9]' 组成，长度为 7。

现在让我们考虑另一个例子来演示一种场景。

例如；

如果我们给定一个数组 'arr = [3, 2, 1, 4, 5, 6, 7, 8, 7]'，在这种情况下，最长的湍流子数组将是 '[3, 2, 1, 4, 5, 6, 7, 8]'，长度为八。

以下是我们如何确认该子数组满足湍流条件；

“3 > 2”（递减；零位置的偶数索引）
“2 > 1”（递减；一位置的奇数索引）
“1 < 4”（递增；二位置的偶数索引）
“4 < 5”（递增；三位置的索引）
“5 < 6”（递增；四位置的偶数索引）

此时，我们有比较“6 < 7”，在索引 5 处呈递增趋势。

6. 接下来，我们有“7 < 8”，在索引 6 处呈递增。

在这种情况下，数字 7 不满足湍流准则，因为它小于 8。已相应记录数字 7 的位置。因此，最长的湍流序列是 [3, 2, 1, 4, 5, 6, 7, 8]，共包含八个元素。

这些例子说明，湍流序列可以在给定数组中的任何连接处开始和结束，并且可以包含元素，只要它们遵守湍流条件。

方法

让我们考虑三种方法来解决识别子数组的问题。以下是我们可以探索的三种方法；

1. 暴力法

在暴力策略中，我们检查给定数组中的每个子数组以识别湍流子数组。为此，我们检查每个子数组并验证它是否满足湍流的条件。此方法的时间复杂度为 **O(n^3)**，其中 n 是输入数组的大小，这使得它无法有效处理数组。

2. 双指针技术

双指针技术涉及使用两个指针，分别称为“start”和“end”，来跟踪子数组。最初，'start' 和 'end' 指针都设置为数组索引。之后，我们向前移动“end”指针，直到它不再满足湍流条件。如果违反此条件，我们将“start”指针调整到发生违规的点，并继续前进“end”指针。在此过程中，我们记录已识别的子数组。此方法的时间复杂度为 **O(n)**，其中 n 代表输入数组的长度，比其他方法更有效。

3. 动态规划

动态规划涉及将问题分解成部分，并将这些部分的解决方案存储在缓存或数据结构中。

使用一个名为 **'dp[i][j]'** 的状态来表示以索引 'j' 结尾的子数组的长度，其中包含索引 'i' 的状态（递增或递减）。我们可以利用 'dp[i 1][j 1]' 的值来确定 'dp[i][j]' 的值。然后，考虑 'arr[i 1]' 与 'arr[j]' 的关系。子数组的长度由 'dp' 表中的值表示，该值最终为我们提供了结果。

此方法的时间复杂度为 **O(n^2)**，其中 n 代表输入数组的长度，空间复杂度为 O(n^2) 用于 'dp' 表。

在这些技术中，双指针策略通常被认为是解决此问题的首选方案。它在时间复杂度方面是有效的，并且不消耗空间。

暴力法由于其立方时间复杂度，在处理输入数组时效率低下。另一方面，动态规划方法可能适用于某些场景，但需要额外的空间来存储 **'dp'** 表。

重要的是要考虑，选择一种方法也可能取决于问题的要求，例如我们是否需要输出子数组或仅输出其长度，以及可能需要的任何其他约束或优化。

示例

让我们以一个例子来说明如何在 C++ 中查找 **最长湍流子数组**。

 
#include <iostream>
#include <vector>

using namespace std;

int maxTurbulenceSize(vector<int>& arr) {
    int n = arr.size();
    if (n < 2) {
        return n;  // Empty or single-element array is considered a turbulent subarray
    }

    int maxLen = 1;  // Initialize the maximum length to 1
    int start = 0;   // Start pointer of the current turbulent subarray
    int end = 1;     // End pointer of the current turbulent subarray

    while (end < n) {
        if (arr[end] == arr[end - 1]) {
            // If the current element is equal to the previous element,
            // reset the start pointer to the current end pointer
            start = end;
        } else if ((end - start >= 2) &&
                   (arr[end] < arr[end - 1]) == (arr[end - 1] < arr[end - 2])) {
            // If the current element violates the turbulence condition,
            // update the start pointer to the index where the violation occurred
            start = end - 1;
        }

        maxLen = max(maxLen, end - start + 1);  // Update the maximum length
        end++;  // Move the end pointer forward
    }

    return maxLen;
}

int main() {
    vector<int> arr1 = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    vector<int> arr2 = {4, 8, 12, 16};
    vector<int> arr3 = {1, 5, 3, 7, 4, 6, 9, 2, 8};
    vector<int> arr4 = {3, 2, 1, 4, 5, 6, 7, 8, 7};

    cout << "Length of the longest turbulent subarray in arr1: " << maxTurbulenceSize(arr1) << endl;
    cout << "Length of the longest turbulent subarray in arr2: " << maxTurbulenceSize(arr2) << endl;
    cout << "Length of the longest turbulent subarray in arr3: " << maxTurbulenceSize(arr3) << endl;
    cout << "Length of the longest turbulent subarray in arr4: " << maxTurbulenceSize(arr4) << endl;

    return 0;
}   

输出

 
Length of the longest turbulent subarray in arr1: 5
Length of the longest turbulent subarray in arr2: 2
Length of the longest turbulent subarray in arr3: 6
Length of the longest turbulent subarray in arr4: 3

说明

以下是代码的逐步分解；

首先，确定输入数组的大小，然后将其保存在名为 'n' 的变量中。
如果 'n' 大于 2，则返回 'n'，因为单元素数组被视为湍流子数组。
接下来，设置一个名为 'maxLen' 的变量为 1，以跟踪到目前为止找到的子数组。
然后，初始化两个指针 'start' 和 'end' 分别为 0 和 1，表示湍流子数组的开始和结束索引。
创建一个循环，直到 'end' 指针到达数组末尾。
在循环内，考虑以下情况；
1. 如果当前元素 ('arr[end]') 与元素 ('arr[end. 1]') 匹配，则将 'start' 指针重置为与 'end' 指示的位置匹配。
2. 如果当前段违反了预期的湍流模式，则起始点和结束点之间至少存在两个段。将起始点调整到发生不匹配的位置（在 'end. 1'）。
3. 如果以上两种情况都不适用，则无需进一步操作。
更新 'variable 以反映哪个值更大；它的值或当前湍流段的长度 ('end. Start + 1')。
通过递增来向前移动 'end' 指针。
循环结束后，返回 'maxLen' 变量，它表示在输入数组中找到的最长湍流子数组的长度。

这些步骤概述了用于有效查找最长湍流子数组长度的双指针方法，其时间复杂度为 O(n)，空间复杂度为 O(1)。

下一主题Duffinian-numbers-in-cpp

C++ 中查找最长湍流子数组

问题描述

示例；