最长湍流子数组的最大长度问题 题目描述： 给定一个整数数组 arr，如果比较符号在子数组中的每个相邻元素对之间翻转（即 >、<、>、<... 或 <、>、 <、>...），则该子数组为湍流子数组。返回 arr 的最大湍流子数组的长度。 示例： 输入：arr = [ 9,4,2,10,7,8,8,1,9 ] 输出：5 解释：arr[ 1] > arr[ 2] < arr[ 3] > arr[ 4] < arr[ 5 ] 解题过程： 问题分析： 我们需要找到最长的连续子数组，其中相邻元素的比较关系交替变化 湍流条件：对于索引 i，需要满足： 如果 i 是奇数：arr[ i] > arr[ i+1] 且 arr[ i] > arr[ i-1 ] 如果 i 是偶数：arr[ i] < arr[ i+1] 且 arr[ i] < arr[ i-1 ] 或者相反的模式 状态定义： 定义两个状态数组： up[ i]: 以位置 i 结尾，且 arr[ i] > arr[ i-1 ] 的最长湍流子数组长度 down[ i]: 以位置 i 结尾，且 arr[ i] < arr[ i-1 ] 的最长湍流子数组长度 状态转移方程： 对于每个位置 i (i ≥ 1)： 如果 arr[ i] > arr[ i-1 ]： up[ i] = down[ i-1 ] + 1 // 前一个位置是下降，现在上升 down[ i ] = 1 // 重置下降序列 如果 arr[ i] < arr[ i-1 ]： down[ i] = up[ i-1 ] + 1 // 前一个位置是上升，现在下降 up[ i ] = 1 // 重置上升序列 如果 arr[ i] == arr[ i-1 ]： up[ i ] = 1 // 重置 down[ i ] = 1 // 重置 边界条件： 当数组长度为 1 时，最大长度为 1 up[ 0] = 1, down[ 0 ] = 1 算法步骤： 步骤 1：初始化 如果数组为空，返回 0 如果数组长度为 1，返回 1 初始化 up[ 0] = 1, down[ 0 ] = 1 初始化最大长度 max_ len = 1 步骤 2：遍历处理 对于 i 从 1 到 n-1： 如果 arr[ i] > arr[ i-1 ]： up[ i] = down[ i-1 ] + 1 down[ i ] = 1 否则如果 arr[ i] < arr[ i-1 ]： down[ i] = up[ i-1 ] + 1 up[ i ] = 1 否则： up[ i ] = 1 down[ i ] = 1 步骤 3：更新最大值 max_ len = max(max_ len, up[ i], down[ i ]) 示例推导： arr = [ 9,4,2,10,7,8,8,1,9 ] i=1: 4<9 → down[ 1]=up[ 0]+1=2, up[ 1]=1, max_ len=2 i=2: 2<4 → down[ 2]=up[ 1]+1=2, up[ 2]=1, max_ len=2 i=3: 10>2 → up[ 3]=down[ 2]+1=3, down[ 3]=1, max_ len=3 i=4: 7<10 → down[ 4]=up[ 3]+1=4, up[ 4]=1, max_ len=4 i=5: 8>7 → up[ 5]=down[ 4]+1=5, down[ 5]=1, max_ len=5 i=6: 8=8 → up[ 6]=1, down[ 6]=1, max_ len=5 i=7: 1<8 → down[ 7]=up[ 6]+1=2, up[ 7]=1, max_ len=5 i=8: 9>1 → up[ 8]=down[ 7]+1=3, down[ 8]=1, max_ len=5 复杂度分析： 时间复杂度：O(n)，只需遍历数组一次 空间复杂度：O(n)，可以使用两个状态数组，也可以优化到 O(1) 这种动态规划解法通过维护上升和下降两种状态，巧妙地捕捉了湍流子数组的交替特性。