题目：最长湍流子数组（Longest Turbulent Subarray）

问题描述：

给定一个整数数组 arr，定义一个子数组为“湍流子数组”的条件是：在子数组中，相邻元素的比较符号在“大于”和“小于”之间严格交替。例如，对于子数组 [arr[i], arr[i+1], ..., arr[j]]，对于任意索引 k（i ≤ k < j），都有：

• 当 k 为奇数时，arr[k] > arr[k+1]；
• 当 k 为偶数时，arr[k] < arr[k+1]；

或者反过来：

• 当 k 为奇数时，arr[k] < arr[k+1]；
• 当 k 为偶数时，arr[k] > arr[k+1]。

也就是说，相邻元素的大小关系必须严格交替变化（不能相等），且交替的模式从第一个相邻对开始可以是“升-降”或“降-升”。

请你返回 arr 中最长湍流子数组的长度。

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：最长湍流子数组是 [4,2,10,7,8]，因为：
4 > 2（降），2 < 10（升），10 > 7（降），7 < 8（升），8 和 8 相等（不满足交替，子数组到此结束）。
注意，[2,10,7,8] 也是湍流子数组，但长度只有 4。

示例 2：

输入：arr = [4,8,12,16]
输出：2
解释：任何长度大于 2 的子数组都不满足交替条件，因为相邻元素都递增（4<8<12<16），没有下降。
最长湍流子数组可以是 [4,8] 或 [8,12] 或 [12,16]，长度均为 2。

示例 3：

输入：arr = [100]
输出：1
解释：单个元素被视为长度为 1 的湍流子数组。

约束条件：

• 1 <= arr.length <= 4 * 10^4
• 0 <= arr[i] <= 10^9

解题过程（循序渐进）：

步骤 1：理解问题本质

题目要求找最长连续子数组，其中相邻元素的大小关系必须“升-降-升-降…”或“降-升-降-升…”严格交替，且相邻元素不能相等（相等会破坏交替）。

这本质上是一个线性动态规划问题，因为我们可以从左到右遍历数组，根据当前元素与前一个元素的关系，决定当前能否延续之前的湍流模式。

步骤 2：定义状态

我们可以定义两个状态数组（也可以只用两个变量），分别表示以当前位置 i 结尾的湍流子数组的两种可能模式：

• up[i]：表示以 arr[i] 结尾，且最后一步是“上升”（即 arr[i-1] < arr[i]）的湍流子数组的长度。
• down[i]：表示以 arr[i] 结尾，且最后一步是“下降”（即 arr[i-1] > arr[i]）的湍流子数组的长度。

为什么需要两个状态？因为湍流要求交替，如果当前是“上升”，那么前一步必须是“下降”；反之，如果当前是“下降”，前一步必须是“上升”。

步骤 3：状态转移方程

对于位置 i（i ≥ 1）：

1. 如果 arr[i-1] < arr[i]（上升）：

   • 当前想要以“上升”结束，那么前一步必须以“下降”结束，所以 up[i] = down[i-1] + 1。
   • 此时“下降”无法延续（因为当前是上升），所以 down[i] = 1（因为单个元素 arr[i] 本身可以视为一个湍流子数组，但这里我们通常将 down[i] 重置为 1，表示重新开始；更准确地说，当 arr[i-1] < arr[i] 时，down[i] 不能从前面延续下降模式，只能为 1）。

2. 如果 arr[i-1] > arr[i]（下降）：

   • 当前想要以“下降”结束，那么前一步必须以“上升”结束，所以 down[i] = up[i-1] + 1。
   • 此时“上升”无法延续，所以 up[i] = 1。

3. 如果 arr[i-1] == arr[i]（相等）：

   • 无论上升还是下降模式都无法延续，所以 up[i] = 1，down[i] = 1。

注意：长度为 1 的子数组总是湍流的，所以我们初始化所有 up[i] = 1，down[i] = 1。

步骤 4：初始化

对于 i = 0（第一个元素）：

• up[0] = 1
• down[0] = 1

因为单个元素本身就是湍流子数组。

步骤 5：遍历与更新答案

我们从 i = 1 开始遍历数组，根据上述转移方程更新 up[i] 和 down[i]，同时记录最大值 max_len = max(max_len, up[i], down[i])。

步骤 6：举例推导

以 arr = [9,4,2,10,7,8,8,1,9] 为例：

初始化：up[0]=1, down[0]=1, max_len=1

• i=1: arr[0]=9, arr[1]=4 (下降)

  • down[1] = up[0] + 1 = 2
  • up[1] = 1
  • max_len = max(1,2,1) = 2

• i=2: arr[1]=4, arr[2]=2 (下降)

  • down[2] = up[1] + 1 = 2（因为 up[1]=1）
  • up[2] = 1
  • max_len = 2

• i=3: arr[2]=2, arr[3]=10 (上升)

  • up[3] = down[2] + 1 = 2+1=3
  • down[3] = 1
  • max_len = 3

• i=4: arr[3]=10, arr[4]=7 (下降)

  • down[4] = up[3] + 1 = 3+1=4
  • up[4] = 1
  • max_len = 4

• i=5: arr[4]=7, arr[5]=8 (上升)

  • up[5] = down[4] + 1 = 4+1=5
  • down[5] = 1
  • max_len = 5

• i=6: arr[5]=8, arr[6]=8 (相等)

  • up[6] = 1
  • down[6] = 1
  • max_len = 5

• i=7: arr[6]=8, arr[7]=1 (下降)

  • down[7] = up[6] + 1 = 1+1=2
  • up[7] = 1
  • max_len = 5

• i=8: arr[7]=1, arr[8]=9 (上升)

  • up[8] = down[7] + 1 = 2+1=3
  • down[8] = 1
  • max_len = 5

最终结果为 5，符合示例。

步骤 7：空间优化

由于 up[i] 和 down[i] 只依赖于前一个状态，我们可以用两个变量 up 和 down 代替数组，在遍历时更新它们。

步骤 8：代码实现（伪代码）

function longestTurbulentSubarray(arr):
    n = arr.length
    if n == 1:
        return 1
    
    up = 1, down = 1
    max_len = 1
    
    for i from 1 to n-1:
        if arr[i-1] < arr[i]:          # 上升
            up = down + 1
            down = 1
        elif arr[i-1] > arr[i]:        # 下降
            down = up + 1
            up = 1
        else:                          # 相等
            up = 1
            down = 1
        
        max_len = max(max_len, up, down)
    
    return max_len

步骤 9：复杂度分析

• 时间复杂度：O(n)，只需一次遍历。
• 空间复杂度：O(1)，只用了常数个变量。

总结：

这道题通过定义两种状态（以当前元素结尾的“上升”模式和“下降”模式），利用相邻元素的大小关系进行状态转移，巧妙地捕捉了湍流子数组的交替特性。最终通过一次扫描即可得到最长长度，是线性动态规划的经典应用。