最长湍流子数组 题目描述 给定一个整数数组 arr ，我们定义一个“湍流子数组”为：该子数组相邻元素之间的比较符号在“大于”和“小于”之间严格交替出现。换句话说，当子数组索引为 i 时（ i 从子数组的起始位置开始计数），满足以下条件之一： 当 i 是奇数时， arr[i] > arr[i+1] ，而当 i 是偶数时， arr[i] < arr[i+1] 。 或者，当 i 是奇数时， arr[i] < arr[i+1] ，而当 i 是偶数时， arr[i] > arr[i+1] 。 你也可以简单地理解为：对于子数组中连续的三个元素 arr[k] , arr[k+1] , arr[k+2] （如果存在），它们之间的关系应该是： 如果 arr[k] < arr[k+1] ，那么 arr[k+1] > arr[k+2] 。 如果 arr[k] > arr[k+1] ，那么 arr[k+1] < arr[k+2] 。 题目要求你找出 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：定义状态 我们需要描述以某个位置结尾的子数组的湍流性质。我们可以定义两个状态数组： dp_up[i] ：表示以索引 i 结尾，并且最后两个元素的关系是 arr[i-1] < arr[i] （即“上升”）的最长湍流子数组的长度。 dp_down[i] ：表示以索引 i 结尾，并且最后两个元素的关系是 arr[i-1] > arr[i] （即“下降”）的最长湍流子数组的长度。 为什么需要两个状态？因为湍流的定义是交替的。一个有效的湍流子数组，其结尾的趋势（上升或下降）决定了前一个趋势应该是什么。 步骤2：状态转移方程 现在我们来思考，如何根据已知的前一个状态来推导当前状态。 对于 dp_up[i] （我们希望 arr[i-1] < arr[i] ） ： 要想形成以 i 结尾的“上升”趋势，并且整个子数组是湍流的，那么在 i-1 位置，趋势必须是“下降”。也就是说，在 i-1 之前，应该是 arr[i-2] > arr[i-1] 。 因此，如果 arr[i-1] < arr[i] 成立，那么 dp_up[i] = dp_down[i-1] + 1 。这表示我们在以 i-1 结尾的“下降”湍流子数组后面，添加了一个“上升”趋势，使得湍流得以延续。 如果 arr[i-1] 和 arr[i] 不满足“上升”关系，那么以 i 结尾的“上升”湍流子数组就无法由前一个状态转移过来，只能从它自己开始，长度为1（单个元素本身可以看作一个平凡的湍流子数组）。但这里有一个细节，我们稍后在初始化步骤中统一处理。 对于 dp_down[i] （我们希望 arr[i-1] > arr[i] ） ： 同理，要想形成以 i 结尾的“下降”趋势，那么在 i-1 位置，趋势必须是“上升”。也就是说，在 i-1 之前，应该是 arr[i-2] < arr[i-1] 。 因此，如果 arr[i-1] > arr[i] 成立，那么 dp_down[i] = dp_up[i-1] + 1 。 同样，如果不满足关系，则无法从之前的状态转移。 特殊情况：当 arr[i-1] == arr[i] ： 如果相邻元素相等，那么无论之前是什么趋势，到这里都断掉了。因为湍流要求严格的大于或小于。所以此时， dp_up[i] 和 dp_down[i] 都应该重置为1。 综合起来，状态转移方程如下： 对于每个位置 i （从1开始遍历）： 如果 arr[i] > arr[i-1] : dp_up[i] = dp_down[i-1] + 1 // 当前是上升，继承自之前的下降趋势 dp_down[i] = 1 // 当前不满足下降趋势，下降序列只能从自己开始 如果 arr[i] < arr[i-1] : dp_down[i] = dp_up[i-1] + 1 // 当前是下降，继承自之前的上升趋势 dp_up[i] = 1 // 当前不满足上升趋势，上升序列只能从自己开始 如果 arr[i] == arr[i-1] : dp_up[i] = 1 dp_down[i] = 1 为什么在情况1中要把 dp_down[i] 设为1，情况2中把 dp_up[i] 设为1？ 因为当条件不满足时，以 i 结尾的、符合另一种趋势的湍流子数组无法从前面延伸过来，只能以自己为起点。例如，在情况1中，我们无法形成一个以 i 结尾且最后是下降趋势的湍流子数组（因为实际是上升的），所以 dp_down[i] 只能是1（单个元素）。 步骤3：初始化 我们需要考虑数组的起始位置。 对于第一个元素（ i=0 ），它前面没有元素可以比较。所以，以它结尾的湍流子数组长度就是1。 因此，我们可以初始化 dp_up[0] = 1 和 dp_down[0] = 1 。 这样，当我们从 i=1 开始遍历时，就可以正确地应用状态转移方程。 步骤4：计算顺序 我们从头到尾遍历数组，即从 i=1 遍历到 i = n-1 （ n 是数组长度）。在遍历每个位置 i 时，根据 arr[i] 和 arr[i-1] 的大小关系，来更新 dp_up[i] 和 dp_down[i] 。 步骤5：获取结果 最终答案不是 dp_up[n-1] 或 dp_down[n-1] ，而是整个 dp_up 和 dp_down 数组中的最大值。因为最长的湍流子数组可能出现在数组的任何一个位置。 算法步骤总结（伪代码） 设 n 为数组 arr 的长度。 如果 n == 0 ，返回0。如果 n == 1 ，返回1。 初始化两个数组 dp_up 和 dp_down ，长度都为 n 。 设置 dp_up[0] = 1 , dp_down[0] = 1 。 初始化一个变量 max_len = 1 用来记录最终答案。 从 i = 1 遍历到 n-1 ： a. 如果 arr[i] > arr[i-1] : - dp_up[i] = dp_down[i-1] + 1 - dp_down[i] = 1 b. 否则，如果 arr[i] < arr[i-1] : - dp_down[i] = dp_up[i-1] + 1 - dp_up[i] = 1 c. 否则（ arr[i] == arr[i-1] ）: - dp_up[i] = 1 - dp_down[i] = 1 d. 更新 max_len = max(max_len, dp_up[i], dp_down[i]) 返回 max_len 。 空间优化 注意到在计算 dp_up[i] 和 dp_down[i] 时，我们只依赖于 dp_up[i-1] 和 dp_down[i-1] 。因此，我们可以不使用两个数组，而只使用两个变量来记录前一个状态，从而将空间复杂度从 O(n) 降低到 O(1)。 优化后的伪代码： n = len(arr) 如果 n <= 1 ，返回 n 。 初始化 dp_up = 1 , dp_down = 1 。 初始化 max_len = 1 。 从 i = 1 遍历到 n-1 ： a. 如果 arr[i] > arr[i-1] : - new_dp_up = dp_down + 1 - new_dp_down = 1 b. 否则，如果 arr[i] < arr[i-1] : - new_dp_down = dp_up + 1 - new_dp_up = 1 c. 否则: - new_dp_up = 1 - new_dp_down = 1 d. 更新 dp_up = new_dp_up , dp_down = new_dp_down 。 e. max_len = max(max_len, dp_up, dp_down) 返回 max_len 。 示例演示（使用优化后方法） arr = [9,4,2,10,7,8,8,1,9] 初始化： dp_up = 1 , dp_down = 1 , max_len = 1 i=1: arr[ 1]=4, arr[ 0]=9 -> 4 < 9 (下降) new_dp_down = dp_up(1) + 1 = 2 new_dp_up = 1 更新： dp_up=1 , dp_down=2 , max_len = max(1,1,2)=2 i=2: arr[ 2]=2, arr[ 1]=4 -> 2 < 4 (下降？注意，我们需要看当前趋势和前一趋势。前一趋势是下降，但当前 2<4 是上升？不，这里需要仔细：我们比较的是 arr[i] 和 arr[i-1] ，即 arr[2] 和 arr[1] 。 2 < 4 是上升趋势。) 关系：上升 ( 2 < 4 不成立？ 2 <4 成立，是上升) new_dp_up = dp_down(2) + 1 = 3 (因为前一个状态是下降，长度为2，现在接一个上升) new_dp_down = 1 更新： dp_up=3 , dp_down=1 , max_len = max(2,3,1)=3 此时湍流子数组是 [4,2] ? 不对。 dp_up[2]=3 对应的是 [9,4,2] ? 检查： 9>4 （下降）， 4>2 （下降）。这并不交替！说明我们的理解有误。 关键点纠正： 让我们重新审视状态定义： dp_up[i] ：以 i 结尾，并且 arr[i-1] < arr[i] （即最后是上升）。 dp_down[i] ：以 i 结尾，并且 arr[i-1] > arr[i] （即最后是下降）。 在 i=2 时，我们比较的是 arr[1] 和 arr[2] ，即 4 和 2 。 4 > 2 ，这是一个下降趋势。 所以应该是： i=2: arr[ 2]=2, arr[ 1 ]=4 -> 4 > 2 (下降) 关系：下降 new_dp_down = dp_up(1) + 1 ? 我们看前一个状态 i=1 时是什么。 在 i=1 时，趋势是下降（ 9>4 ），所以 i=1 的状态是 dp_down=2 , dp_up=1 。 对于当前的下降趋势，它应该从之前的上升趋势转移过来。所以我们看 i=1 时的 dp_up ，其值为1。 new_dp_down = dp_up(1) + 1 = 1 + 1 = 2 new_dp_up = 1 (因为当前不是上升) 更新： dp_up=1 , dp_down=2 , max_len = max(3,1,2)=3 ? 这里 max_ len 还是3，但序列是 [9,4,2] ，其关系是 9>4 , 4>2 ，都是下降，不是湍流。 问题根源： 我们的状态定义依赖于相邻两个元素的关系。但是，一个长度为2的子数组，比如 [9,4] ，它本身（只有一种比较关系）可以被视为一个平凡的湍流子数组吗？题目通常允许长度为2的子数组，只要两个元素不相等。所以 [9,4] (9>4) 是有效的，长度为2。 [4,2] (4>2) 也是有效的，长度为2。但是 [9,4,2] (9>4, 4>2) 不是有效的，因为趋势没有交替。 在我们的状态转移中，当我们计算 i=2 时，我们试图将下降趋势 ( 4>2 ) 连接到 i=1 的结尾。i=1 的结尾趋势是下降( 9>4 )。根据湍流定义，在下降趋势之后不能接另一个下降趋势。所以，正确的状态转移应该是： 只有当当前趋势与前一个结尾的趋势相反时，才能延续 。 然而，在我们的状态转移方程中，我们强制性地进行了连接： 在 i=2，当前是下降，我们使用了 dp_up[i-1] 。但在 i=1 时， dp_up[1] 是1，这表示以索引1结尾的一个“上升”趋势的湍流子数组长度是1（即只有 arr[1] 自己）。这实际上是不合理的，因为对于索引1，其真实趋势是下降（ 9>4 ），所以它的 dp_up[1] 不应该是1，而应该是1（表示无法从前面继承上升趋势，只能自己开始）。这个设计本身是合理的。 关键在于 ：当我们使用 dp_up[i] = dp_down[i-1] + 1 时，我们 隐含了一个假设 ，即前一个状态 dp_down[i-1] 所代表的子数组的结尾趋势是下降，这与当前我们想要的上升趋势是交替的，所以可以连接。这个逻辑是正确的。 那么为什么 [9,4,2] 会被计算出长度3？因为我们在 i=1 时， dp_down[1] = 2 ，这表示子数组 [9,4] 是有效的（长度为2）。在 i=2 时，当前是下降，我们本应使用 dp_up[1] ，其值为1，得到 new_dp_down = 1 + 1 = 2 。这个2表示的是 [4,2] 这个子数组（长度为2），而不是 [9,4,2] （长度为3）！ 我们之前的演示计算错了 。 让我们重新正确计算一遍： arr = [9,4,2,10,7,8,8,1,9] 初始化： up = 1 , down = 1 , max_len = 1 i=1: 比较 arr[ 1]和arr[ 0]: 4 < 9? (否，4<9为真？4<9为真，是上升趋势？ 4 <9 是上升) 关系：上升 ( 4 < 9 ) new_up = down(1) + 1 = 1 + 1 = 2 (从之前的下降趋势‘继承’) new_down = 1 (当前不是下降) 更新: up = 2 , down = 1 , max_len = max(1,2,1)=2 解释：以索引1结尾的上升湍流子数组是 [9,4] ？不对， 9>4 是下降！这里出现了根本性的错误。 最核心的纠正： 状态 dp_up[i] 的定义是：以索引 i 结尾，并且最后两个元素的关系是 arr[i-1] < arr[i] （即“上升”）。 这里的关键是 arr[i-1] 和 arr[i] 的关系。 在 i=1 时，我们看的是 arr[0] 和 arr[1] 的关系，即 9 和 4 。 9 < 4 ？ 错误。 9 > 4 正确。 所以，在 i=1 时， arr[0] 和 arr[1] 的关系是 下降 ( 9 > 4 )。 因此，在 i=1： 这是下降趋势。 所以应该走状态转移的第二种情况： arr[i] < arr[i-1] ? 不，我们比较的是 arr[i-1] 和 arr[i] ，即 arr[0] 和 arr[1] 。 arr[0] (9) > arr[1] (4) -> 这是下降趋势。 对于下降趋势： new_down = up_prev + 1 在 i=0 时， up_prev 是1。 所以 new_down = 1 + 1 = 2 new_up = 1 更新后： up = 1 , down = 2 , max_len=2 。 这表示以索引1结尾的、最后为下降趋势的湍流子数组是 [9,4] ，长度为2。这是合理的。 现在 i=2：比较 arr[1] 和 arr[2] ，即 4 和 2 。 4 > 2 -> 下降趋势。 对于下降趋势： new_down = up_prev + 1 前一个状态（i=1）的 up_prev 是1。 所以 new_down = 1 + 1 = 2 new_up = 1 更新： up = 1 , down = 2 , max_len = max(2, 1, 2) = 2 这表示以索引2结尾的、最后为下降趋势的湍流子数组是 [4,2] ，长度为2。它没有和 [9,4] 连接起来，因为连接需要前一个趋势是上升，而 [9,4] 的趋势是下降。所以是独立的子数组 [4,2] 。正确。 i=3：比较 arr[2] 和 arr[3] ，即 2 和 10 。 2 < 10 -> 上升趋势。 对于上升趋势： new_up = down_prev + 1 前一个状态（i=2）的 down_prev 是2。 所以 new_up = 2 + 1 = 3 new_down = 1 更新： up = 3 , down = 1 , max_len = max(2, 3, 1) = 3 这表示以索引3结尾的、最后为上升趋势的湍流子数组是 [4,2,10] 。关系是：4>2（下降），2 <10（上升）。交替成功，长度为3。 i=4：比较 arr[3] 和 arr[4] ，即 10 和 7 。 10 > 7 -> 下降趋势。 对于下降趋势： new_down = up_prev + 1 前一个状态（i=3）的 up_prev 是3。 所以 new_down = 3 + 1 = 4 new_up = 1 更新： up = 1 , down = 4 , max_len = max(3, 1, 4) = 4 序列： [4,2,10,7] ，关系：4>2(降), 2 <10(升), 10>7(降)。交替，长度为4。 i=5：比较 arr[4] 和 arr[5] ，即 7 和 8 。 7 < 8 -> 上升趋势。 对于上升趋势： new_up = down_prev + 1 前一个状态（i=4）的 down_prev 是4。 所以 new_up = 4 + 1 = 5 new_down = 1 更新： up = 5 , down = 1 , max_len = max(4, 5, 1) = 5 序列： [4,2,10,7,8] ，关系：4>2(降), 2<10(升), 10>7(降), 7 <8(升)。交替，长度为5。这就是答案。 i=6：比较 arr[5] 和 arr[6] ，即 8 和 8 。 相等。 new_up = 1 , new_down = 1 更新： up=1 , down=1 , max_len=5 （不变） i=7：比较 arr[6] 和 arr[7] ，即 8 和 1 。 8 > 1 -> 下降趋势。 对于下降趋势： new_down = up_prev + 1 = 1 + 1 = 2 new_up = 1 更新： up=1 , down=2 , max_len=5 i=8：比较 arr[7] 和 arr[8] ，即 1 和 9 。 1 < 9 -> 上升趋势。 对于上升趋势： new_up = down_prev + 1 = 2 + 1 = 3 new_down = 1 更新： up=3 , down=1 , max_len=5 最终结果为5。 希望这个详细的、带有纠错过程的讲解能帮助你彻底理解这个算法。