如何以O(n)时间复杂度查找并返回最长湍流子序列

原有实现问题 #

给出的双层循环实现通过枚举所有子数组起点、逐位扩展终点的方式查找最长湍流，时间复杂度为O(n²)，存在大量重复的相邻元素比较操作。实际上湍流序列的连续性特征支持我们通过单次遍历完成计算，不需要回溯遍历指针，即可将时间复杂度降到O(n)。

湍流判定规则 #

先明确湍流序列的判定标准：

• 单个元素天然是湍流序列
• 长度为2的序列，只要两个元素不相等即为湍流
• 长度≥3的序列，相邻元素的升降方向必须严格交替，不能出现连续上升或连续下降

O(n)算法核心逻辑 #

全程只做一次从左到右的遍历，维护当前统计段、历史最长段的起止位置，以及上一组相邻元素的升降方向即可，不需要回退指针：

• 每向右移动一位，先对比当前元素和前一个元素的升降方向
• 如果当前方向和上一组方向相反，说明当前湍流段可以继续延长，直接更新段终点即可
• 如果当前方向和上一组方向相同（连续升/连续降），说明当前段在前一位已经截断，新的湍流段起点移动到前一位，重新开始统计
• 如果当前元素和前一个元素相等，说明当前位置无法和前一位构成有效湍流，新的湍流段直接从当前位置开始
• 每次更新段长度后，和已记录的最长段比较，更新最长段的起止下标

优化后完整C++代码 #

#include <iostream>
#include <utility>
using namespace std;

pair<int, int> findLongestTurbulence(int arr[], int n) {
    // 边界处理：数组为空直接返回
    if (n == 0) return {0, -1};
    // 初始化最长段、当前段的起止下标
    int maxStart = 0, maxEnd = 0;
    int curStart = 0;
    // 上一组相邻的比较方向：-1未初始化 0下降 1上升
    int lastDir = -1;

    for (int i = 1; i < n; i++) {
        int curDir = -1;
        if (arr[i] > arr[i-1]) curDir = 1;
        else if (arr[i] < arr[i-1]) curDir = 0;
        
        if (curDir == -1) {
            // 当前和前一个元素相等，当前段截断，新段从i开始
            curStart = i;
        } else if (lastDir != -1 && curDir == lastDir) {
            // 方向连续，当前段截断，新段从i-1开始
            curStart = i-1;
        }
        // 方向交替的情况，直接延长当前段即可，不需要改动curStart
        lastDir = curDir;
        // 对比更新最长段
        if (i - curStart > maxEnd - maxStart) {
            maxStart = curStart;
            maxEnd = i;
        }
    }
    return {maxStart, maxEnd};
}

int main()
{
    int arr[] = {1,8,5,2,6,3,9,7,4,2,3};
    int n = sizeof(arr)/sizeof(arr[0]);
    pair<int,int> ans = findLongestTurbulence(arr,n);
    
    for(int i=ans.first;i<ans.second;i++){
        cout<<arr[i]<<", ";
    }
    cout<<arr[ans.second]<<endl;
    // 输出结果为5, 2, 6, 3, 9, 7，符合预期
}

复杂度说明 #

• 时间复杂度：O(n)，全程仅对数组做一次遍历，每个元素仅访问1次，无嵌套循环
• 空间复杂度：O(1)，仅使用固定数量的临时变量，没有额外开辟和数组长度相关的存储空间

内容的提问来源于stack exchange，提问作者Eddy