深入 Java 滑动窗口：「最长湍流子数组」的状态判断与窗口调整

一、问题定义与核心概念

湍流子数组指满足特定交替关系的连续子数组：若相邻元素的大小关系呈周期性变化（即满足 $arr[i] > arr[i+1] < arr[i+2] > \dots$ 或 $arr[i] < arr[i+1] > arr[i+2] < \dots$），则称为湍流子数组。例如数组 $[9,4,2,10,7,8]$ 中，子数组 $[4,2,10,7,8]$ 满足： $$4 > 2 < 10 > 7 < 8$$ 其长度为 5，是最长湍流子数组。

二、滑动窗口算法设计

核心思想：通过双指针动态维护满足湍流条件的窗口，实时调整边界以追踪最大长度。

状态判断关键点

1. 相邻关系符号：定义比较函数 $cmp(a,b)$：
   • $cmp(a,b) > 0$ 表示 $a > b$
   • $cmp(a,b) < 0$ 表示 $a < b$
   • $cmp(a,b) = 0$ 表示 $a = b$
2. 交替性验证：对窗口内连续三元素 $arr[k-2], arr[k-1], arr[k]$，需满足： $$cmp(arr[k-1], arr[k-2]) \times cmp(arr[k], arr[k-1]) < 0$$ 即两次比较结果符号相反。

窗口调整策略

1. 扩展条件：新元素加入后仍满足交替性，右指针 $right$ 右移。
2. 收缩条件：
   • 若 $arr[right] = arr[right-1]$，重置窗口起点（$left = right$）
   • 若连续三次比较符号相同，将左指针移至 $right-1$

三、Java 实现与注释

public int maxTurbulenceSize(int[] arr) {
    int n = arr.length;
    if (n <= 1) return n;
    
    int left = 0, maxLen = 1;
    for (int right = 1; right < n; right++) {
        // 1. 计算当前相邻元素关系
        int currCmp = Integer.compare(arr[right], arr[right-1]);
        
        if (currCmp == 0) {
            // 相等元素破坏湍流，重置窗口起点
            left = right; 
        } else if (right >= 2) {
            // 2. 计算前次相邻关系
            int prevCmp = Integer.compare(arr[right-1], arr[right-2]);
            // 3. 检查交替性：符号需相反
            if (prevCmp * currCmp >= 0) {
                left = right - 1; // 收缩窗口
            }
        }
        // 4. 更新最大窗口长度
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

关键步骤解析

1. 初始化：$left=0$, $maxLen=1$（单元素总满足条件）
2. 遍历：右指针 $right$ 从 1 开始扫描数组
3. 关系计算：
   • currCmp 检测 $arr[right]$ 与 $arr[right-1]$ 关系
   • prevCmp 检测 $arr[right-1]$ 与 $arr[right-2]$ 关系（当 $right \geq 2$）
4. 窗口调整：
   • 出现相等元素时（$currCmp=0$），窗口重置至当前位置
   • 连续两次比较符号相同（$prevCmp \times currCmp \geq 0$），左指针移至 $right-1$
5. 长度更新：实时计算窗口长度 $right - left + 1$

四、复杂度与边界分析

1. 时间复杂度：$O(n)$
   仅需单次遍历数组，每个元素处理 $O(1)$ 时间。
2. 空间复杂度：$O(1)$
   仅使用固定数量的指针变量。
3. 边界处理：
   • 数组长度 $\leq 1$ 时直接返回
   • 全等数组（如 $[2,2,2]$）返回 1
   • 全递减/递增数组（如 $[3,2,1]$）返回 2

五、算法特性总结

1. 动态适应性：窗口根据实时比较关系调整，避免重复验证历史数据。
2. 符号驱动：通过比较结果的符号乘积（$prevCmp \times currCmp$）高效判断交替性。
3. 隐式回溯：当窗口收缩至 $[right-1, right]$ 时，保留最后两个有效元素作为新起点。

应用场景扩展：该滑动窗口模式可推广至所有需验证局部连续关系的子数组问题，如交替二进制串、波形数组等，只需修改状态判断逻辑即可适配。

本文通过拆解湍流子数组的核心特征，结合滑动窗口的状态判断与边界调整策略，实现了高效求解。代码清晰展现了窗口收缩/扩展的触发条件，为处理类似问题提供通用范式。