最长湍流子数组 题目描述 给定一个整数数组arr，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。更形式化地说，对于子数组arr[ i], arr[ i+1], ..., arr[ j ]： 当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中最长湍流子数组的长度。 示例 输入：arr = [ 9,4,2,10,7,8,8,1,9 ] 输出：5 解释：最长的湍流子数组是[ 4,2,10,7,8]，对应比较序列：4>2, 2<10, 10>7, 7 <8。 解题过程 步骤1：理解湍流子数组的定义 湍流子数组要求相邻元素的大小关系交替变化。具体来说，对于任意三个连续元素arr[ i-1], arr[ i], arr[ i+1 ]，必须满足以下两种模式之一： arr[ i-1] > arr[ i] 且 arr[ i] < arr[ i+1 ]（下降-上升模式） arr[ i-1] < arr[ i] 且 arr[ i] > arr[ i+1 ]（上升-下降模式） 步骤2：定义状态 我们可以定义两个状态数组： up[ i]：表示以arr[ i]结尾，且arr[ i ]比前一个元素大的最长湍流子数组长度 down[ i]：表示以arr[ i]结尾，且arr[ i ]比前一个元素小的最长湍流子数组长度 步骤3：状态转移方程 对于每个位置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 // 相等时重置为1 down[ i ] = 1 // 相等时重置为1 步骤4：边界条件 对于第一个元素（i = 0）： up[ 0 ] = 1 // 单个元素可以看作长度为1的湍流子数组 down[ 0 ] = 1 步骤5：计算过程 以arr = [ 9,4,2,10,7,8,8,1,9 ]为例： i=0: up=1, down=1, max_ len=1 i=1: 9>4? 是 → down[ 1]=up[ 0]+1=2, up[ 1]=1, max_ len=2 i=2: 4>2? 是 → down[ 2]=up[ 1]+1=2, up[ 2]=1, max_ len=2 i=3: 2<10? 是 → up[ 3]=down[ 2]+1=3, down[ 3]=1, max_ len=3 i=4: 10>7? 是 → down[ 4]=up[ 3]+1=4, up[ 4]=1, max_ len=4 i=5: 7<8? 是 → 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: 8>1? 是 → down[ 7]=up[ 6]+1=2, up[ 7]=1, max_ len=5 i=8: 1<9? 是 → up[ 8]=down[ 7]+1=3, down[ 8]=1, max_ len=5 步骤6：空间优化 由于每个状态只依赖于前一个状态，我们可以用两个变量代替数组： up_ prev, down_ prev：前一个位置的状态 up_ curr, down_ curr：当前位置的状态 最终答案 最长湍流子数组的长度为5，对应子数组[ 4,2,10,7,8 ]。 这个算法的时间复杂度是O(n)，空间复杂度是O(1)（使用空间优化后）。