最长湍流子数组 题目描述 给定一个整数数组 arr ，当 arr 的子数组 A 满足以下条件时，我们称其为湍流子数组： 对于每个索引 i （其中 0 < i < A.length-1 ），比较符号在 A[i-1] 与 A[i] 之间、以及 A[i] 与 A[i+1] 之间是相反的。即： 若 A[i-1] > A[i] ，则 A[i] < A[i+1] ； 若 A[i-1] < A[i] ，则 A[i] > A[i+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：理解问题本质 湍流子数组要求相邻元素的大小关系交替变化（升→降→升… 或 降→升→降…）。注意： 单个元素（长度为1）总是湍流的。 两个元素只要不等（即存在大小关系），也是湍流的。 从第三个元素开始，需要检查交替条件。 步骤2：定义状态 使用动态规划，定义两个状态数组： up[i] ：以 arr[i] 结尾，且 arr[i] 比前一个元素 大 的最长湍流子数组长度。 down[i] ：以 arr[i] 结尾，且 arr[i] 比前一个元素 小 的最长湍流子数组长度。 为什么这样定义？因为湍流要求交替，当前状态取决于前一个状态是“上升”还是“下降”。 步骤3：状态转移方程 如果 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] = down[i] = 1 （从当前元素重新开始）。 基础情况 ： 当 i=0 （第一个元素）时， up[0] = down[0] = 1 （单个元素总是湍流）。 步骤4：计算与答案提取 遍历数组，根据上述规则更新 up 和 down 数组。 最终答案是所有 up[i] 和 down[i] 中的最大值。 步骤5：示例推导 以 arr = [9,4,2,10,7,8,8,1,9] 为例： | i | arr[ i] | 与前一个比较 | up[ i] | down[ i ] | 说明 | |---|--------|--------------|-------|---------|------| | 0 | 9 | - | 1 | 1 | 初始 | | 1 | 4 | < | 1 | up[ 0 ]+1=2 | 下降，接在上升后（但前一个没有上升，所以从1开始？注意：这里需要修正逻辑）| 详细推导修正 ： 实际上，对于 i=1： arr[ 1]=4 < arr[ 0]=9 → 下降： down[1] = up[0] + 1 = 2 ， up[1] = 1 。 i=2：arr[ 2]=2 < arr[ 1 ]=4 → 下降： 当前是下降，应接在前一个上升后面，但前一个 up[ 1]=1（没有实际上升），所以 down[2] = up[1] + 1 = 2 。 up[ 2 ]=1。 i=3：arr[ 3]=10 > arr[ 2 ]=2 → 上升： up[3] = down[2] + 1 = 3 （接在前一个下降后面）。 down[ 3 ]=1。 i=4：arr[ 4]=7 < arr[ 3 ]=10 → 下降： down[4] = up[3] + 1 = 4 。 up[ 4 ]=1。 i=5：arr[ 5]=8 > arr[ 4 ]=7 → 上升： up[5] = down[4] + 1 = 5 。 down[ 5 ]=1。 i=6：arr[ 6]=8 == arr[ 5 ]=8 → 相等： up[ 6]=1, down[ 6 ]=1。 i=7：arr[ 7]=1 < arr[ 6 ]=8 → 下降： down[7] = up[6] + 1 = 2 。 up[ 7 ]=1。 i=8：arr[ 8]=9 > arr[ 7 ]=1 → 上升： up[8] = down[7] + 1 = 3 。 down[ 8 ]=1。 最大值出现在 i=5 时， up[5]=5 ，所以答案是 5。 步骤6：复杂度分析 时间复杂度：O(n)，遍历一次数组。 空间复杂度：可优化到 O(1)，因为只需前一个状态。