最长湍流子数组问题（进阶版）

字数 2241 2025-11-27 09:47:30

最长湍流子数组问题（进阶版）

题目描述：
给定一个整数数组 arr，我们需要找到最长的湍流子数组的长度。湍流子数组的定义是：相邻元素的符号在正负之间严格交替。也就是说，对于子数组 arr[i..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]。
但更常见的定义是：比较符号在相邻元素之间交替变化（即 >, <, >, <, ... 或 <, >, <, >, ...）。进阶版中，数组可能包含重复元素，且需要处理更复杂的约束。

解题过程：

问题分析：
湍流子数组要求相邻元素的比较关系（大于或小于）交替变化。例如，[9,4,2,10,7,8,8,1,9] 中，子数组 [4,2,10,7,8] 是湍流的，因为 4 > 2, 2 < 10, 10 > 7, 7 < 8（符号序列：>, <, >, <）。但如果有重复元素（如相邻的 8,8），符号无法定义，湍流条件会中断。
动态规划状态定义：
使用两个 DP 数组：
- up[i]：以索引 i 结尾，且 arr[i] > arr[i-1] 的最长湍流子数组长度。
- down[i]：以索引 i 结尾，且 arr[i] < arr[i-1] 的最长湍流子数组长度。
  对于单个元素，长度总为 1（即 up[i] = down[i] = 1 作为初始条件）。
状态转移方程：
- 如果 arr[i] > arr[i-1]：当前元素大于前一个，湍流模式应接在“下降”模式后（即 down[i-1] 后接上升），所以 up[i] = down[i-1] + 1。而 down[i] 保持为 1（因为当前是上升，不能接在上升后）。
- 如果 arr[i] < arr[i-1]：当前元素小于前一个，湍流模式应接在“上升”模式后（即 up[i-1] 后接下降），所以 down[i] = up[i-1] + 1。而 up[i] 保持为 1。
- 如果 arr[i] == arr[i-1]：符号中断，up[i] 和 down[i] 都重置为 1。
  最终，最长湍流子数组长度是 max(up[i], down[i]) 在所有 i 上的最大值。
计算步骤：
- 初始化：up[0] = 1, down[0] = 1（数组长度 n ≥ 1）。
- 遍历 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
  - 如果 arr[i] == arr[i-1]：
    - up[i] = 1, down[i] = 1
- 同时更新全局最大值 max_len = max(max_len, up[i], down[i])。
示例：
数组 arr = [9,4,2,10,7,8,8,1,9]：
- i=1: 9>4? 否（9>4 为真，但比较是 4<9？这里按顺序：arr[0]=9, arr[1]=4 → 4<9？实际计算时，从 i=1 开始比较 arr[i] 和 arr[i-1]。
  详细计算：
  i=1: arr[1]=4 < arr[0]=9 → down[1] = up[0]+1=2, up[1]=1 → max_len=2。
  i=2: arr[2]=2 < arr[1]=4 → down[2] = up[1]+1=2, up[2]=1 → max_len=2。
  i=3: arr[3]=10 > arr[2]=2 → up[3] = down[2]+1=3, down[3]=1 → max_len=3。
  i=4: arr[4]=7 < arr[3]=10 → down[4] = up[3]+1=4, up[4]=1 → max_len=4。
  i=5: arr[5]=8 > arr[4]=7 → up[5] = down[4]+1=5, down[5]=1 → max_len=5。
  i=6: arr[6]=8 == arr[5]=8 → up[6]=1, down[6]=1 → max_len=5。
  i=7: arr[7]=1 < arr[6]=8 → down[7] = up[6]+1=2, up[7]=1 → max_len=5。
  i=8: arr[8]=9 > arr[7]=1 → up[8] = down[7]+1=3, down[8]=1 → max_len=5。
  结果：最长湍流子数组长度为 5（对应子数组 [4,2,10,7,8]）。
复杂度分析：
- 时间复杂度：O(n)，遍历数组一次。
- 空间复杂度：O(n)（可优化到 O(1) 只保存前一个状态）。

这种方法高效地利用动态规划跟踪交替模式，处理了重复元素导致的中断，适用于进阶版约束。

最长湍流子数组问题（进阶版）题目描述：给定一个整数数组 arr，我们需要找到最长的湍流子数组的长度。湍流子数组的定义是：相邻元素的符号在正负之间严格交替。也就是说，对于子数组 arr[ i..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 ]。但更常见的定义是：比较符号在相邻元素之间交替变化（即 >, <, >, <, ... 或 <, >, <, >, ...）。进阶版中，数组可能包含重复元素，且需要处理更复杂的约束。解题过程：问题分析：湍流子数组要求相邻元素的比较关系（大于或小于）交替变化。例如，[ 9,4,2,10,7,8,8,1,9] 中，子数组 [ 4,2,10,7,8] 是湍流的，因为 4 > 2, 2 < 10, 10 > 7, 7 < 8（符号序列：>, <, >, <）。但如果有重复元素（如相邻的 8,8），符号无法定义，湍流条件会中断。动态规划状态定义：使用两个 DP 数组： up[ i]：以索引 i 结尾，且 arr[ i] > arr[ i-1 ] 的最长湍流子数组长度。 down[ i]：以索引 i 结尾，且 arr[ i] < arr[ i-1 ] 的最长湍流子数组长度。对于单个元素，长度总为 1（即 up[ i] = down[ i ] = 1 作为初始条件）。状态转移方程：如果 arr[ i] > arr[ i-1]：当前元素大于前一个，湍流模式应接在“下降”模式后（即 down[ i-1] 后接上升），所以 up[ i] = down[ i-1] + 1。而 down[ i ] 保持为 1（因为当前是上升，不能接在上升后）。如果 arr[ i] < arr[ i-1]：当前元素小于前一个，湍流模式应接在“上升”模式后（即 up[ i-1] 后接下降），所以 down[ i] = up[ i-1] + 1。而 up[ i ] 保持为 1。如果 arr[ i] == arr[ i-1]：符号中断，up[ i] 和 down[ i ] 都重置为 1。最终，最长湍流子数组长度是 max(up[ i], down[ i ]) 在所有 i 上的最大值。计算步骤：初始化：up[ 0] = 1, down[ 0 ] = 1（数组长度 n ≥ 1）。遍历 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 如果 arr[ i] == arr[ i-1 ]： up[ i] = 1, down[ i ] = 1 同时更新全局最大值 max_ len = max(max_ len, up[ i], down[ i ])。示例：数组 arr = [ 9,4,2,10,7,8,8,1,9 ]： i=1: 9>4? 否（9>4 为真，但比较是 4<9？这里按顺序：arr[ 0]=9, arr[ 1]=4 → 4<9？实际计算时，从 i=1 开始比较 arr[ i] 和 arr[ i-1 ]。详细计算： i=1: arr[ 1]=4 < arr[ 0]=9 → down[ 1] = up[ 0]+1=2, up[ 1]=1 → max_ len=2。 i=2: arr[ 2]=2 < arr[ 1]=4 → down[ 2] = up[ 1]+1=2, up[ 2]=1 → max_ len=2。 i=3: arr[ 3]=10 > arr[ 2]=2 → up[ 3] = down[ 2]+1=3, down[ 3]=1 → max_ len=3。 i=4: arr[ 4]=7 < arr[ 3]=10 → down[ 4] = up[ 3]+1=4, up[ 4]=1 → max_ len=4。 i=5: arr[ 5]=8 > arr[ 4]=7 → up[ 5] = down[ 4]+1=5, down[ 5]=1 → max_ len=5。 i=6: arr[ 6]=8 == arr[ 5]=8 → up[ 6]=1, down[ 6]=1 → max_ len=5。 i=7: arr[ 7]=1 < arr[ 6]=8 → down[ 7] = up[ 6]+1=2, up[ 7]=1 → max_ len=5。 i=8: arr[ 8]=9 > arr[ 7]=1 → up[ 8] = down[ 7]+1=3, down[ 8]=1 → max_ len=5。结果：最长湍流子数组长度为 5（对应子数组 [ 4,2,10,7,8 ]）。复杂度分析：时间复杂度：O(n)，遍历数组一次。空间复杂度：O(n)（可优化到 O(1) 只保存前一个状态）。这种方法高效地利用动态规划跟踪交替模式，处理了重复元素导致的中断，适用于进阶版约束。