最长湍流子数组的变种——最多允许翻转一个子数组的最长湍流子数组

字数 5264 2025-12-10 01:07:59

最长湍流子数组的变种——最多允许翻转一个子数组的最长湍流子数组

题目描述
给定一个整数数组 arr，如果比较符号在数组中每个相邻元素对之间翻转（即 arr[i] < arr[i+1] 且 arr[i+1] > arr[i+2]，或者 arr[i] > arr[i+1] 且 arr[i+1] < arr[i+2]），则该子数组被称为“湍流子数组”。你可以至多翻转任意一个子数组一次（即将该子数组内的所有元素反转顺序），然后返回翻转后可能得到的最长湍流子数组的长度。

示例：
输入：arr = [9,4,2,10,7,8,8,1,9]
解释：如果不翻转，最长湍流子数组为 [4,2,10,7,8] 或 [2,10,7,8]，长度为 5。但翻转某个子数组可能得到更长的湍流子数组。例如翻转子数组 [8,8]（实际上翻转后仍是 [8,8]），无法延长；若翻转 [7,8,8,1] 为 [1,8,8,7]，则可得到更长的湍流子数组 [10,7,1,8,8,7]？我们需系统计算。实际上，该示例中翻转一个子数组可能得到更长湍流子数组，本题目标就是求出这个最大长度。

解题过程循序渐进讲解

步骤 1：理解湍流子数组定义

湍流子数组要求相邻元素之间的比较关系交替变化：

如果 arr[i] < arr[i+1]，则下一个关系应为 arr[i+1] > arr[i+2]（即 >），再下一个为 <，以此类推。
另一种可能是从 > 开始交替。
长度为 1 的子数组视为湍流（因为没有相邻比较）。
长度为 2 的子数组，只要两元素不等（< 或 >），也算湍流。
但题目通常定义湍流需至少三个元素才要求交替，我们这里按 LeetCode 978 原题定义：对于长度 ≥2 的子数组，只要相邻比较符号交替即可；若相邻元素相等，则湍流中断。

步骤 2：先解决无翻转的情况（LeetCode 978 原题）

我们用两个动态规划数组：

up[i]：以 i 结尾，且最后一段比较是上升（arr[i-1] < arr[i]）的最长湍流子数组长度。
down[i]：以 i 结尾，且最后一段比较是下降（arr[i-1] > arr[i]）的最长湍流子数组长度。

转移方程：
如果 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。

最终答案是所有 max(up[i], down[i]) 的最大值。
这样我们能在 O(n) 时间求出无翻转的最长湍流子数组长度。

步骤 3：考虑翻转一个子数组的影响

翻转一个子数组 [l, r] 后，该子数组内的相邻比较关系全部反向（原来 < 变成 >，原来 > 变成 <，相等不变）。
翻转后，原数组被分成三部分：

前缀 [0, l-1]：不变。
翻转段 [l, r]：内部相邻关系反向。
后缀 [r+1, n-1]：不变。

我们需要计算翻转后，跨越这三部分的某个湍流子数组的最大长度。

步骤 4：关键观察

翻转后，湍流子数组可能：

完全位于前缀内部（无影响）。
完全位于翻转段内部（相当于原翻转段内部反向后的湍流长度）。
完全位于后缀内部（无影响）。
跨越前缀与翻转段的边界。
跨越翻转段与后缀的边界。
同时跨越前缀、翻转段、后缀。

但注意：翻转段内部反向，会影响边界处的比较关系方向连续性。

因此，我们需要预处理四个数组，以便快速得到翻转后的湍流长度。

步骤 5：预处理数组

定义：

up_left[i]：以 i 结尾，且最后比较为上升 (arr[i-1] < arr[i]) 的湍流子数组长度（从左边正常计算，即 up[i]）。
down_left[i]：以 i 结尾，且最后比较为下降的湍流子数组长度（即 down[i]）。
up_right[i]：以 i 开头，且第一段比较为上升 (arr[i] < arr[i+1]) 的湍流子数组长度（向右延伸）。
down_right[i]：以 i 开头，且第一段比较为下降 (arr[i] > arr[i+1]) 的湍流子数组长度。

如何求 up_right 和 down_right？
我们可以从右向左 DP：
设 up_right[i] 为从 i 开始向右，满足第一段比较为上升的最长湍流长度。
如果 arr[i] < arr[i+1]，则 up_right[i] = down_right[i+1] + 1；
如果 arr[i] > arr[i+1]，则 down_right[i] = up_right[i+1] + 1；
如果相等，则 up_right[i] = down_right[i] = 1。
注意：up_right[i] 必须满足第一段是上升，所以如果 arr[i] > arr[i+1]，则 up_right[i] = 1。类似地定义 down_right[i]。

更简单的办法：把数组反转后，用 up_left 的逻辑求，再映射回来。但直接推导更直观。

步骤 6：翻转一个子数组 `[l, r]` 后的最长湍流计算

设翻转后数组为 arr'。
在 arr' 中，对于位置 i 和 i+1：

如果 i 和 i+1 都在翻转段内，则比较关系反向。
如果 i 在翻转段内，i+1 在翻转段外，则比较关系取决于原数组的 arr[i] 和 arr[i+1] 的反向？不对，边界处：
翻转段 [l, r]，考虑 l-1 与 l（边界）：
- 在原数组中 arr[l-1] 与 arr[l] 的关系是某个方向。
- 翻转后，arr'[l-1] = arr[l-1]，arr'[l] = arr[r]（因为翻转段反转了，原来 l 位置变成了 arr[r]）。
  所以边界关系改变，不能简单用预处理数组。

因此，更稳健的方法是：枚举所有可能的湍流子数组的起点和终点，检查是否可以通过一次翻转得到，但这样是 O(n²)，太慢。

我们需要 O(n) 或 O(n log n) 的方法。

步骤 7：高效算法思路

考虑翻转后，湍流子数组必定由三部分组成（可能某些部分长度为 0）：

一个从某个点向左延伸的湍流段（在原数组中正常方向）。
中间一段是翻转段的一部分，且其内部在原数组中反向看也是湍流。
一个从某个点向右延伸的湍流段（在原数组中正常方向）。

关键在于：如果我们固定中间翻转段的两个端点 l 和 r，那么：

左延伸段必须与翻转段的第一元素在翻转后的关系匹配。
右延伸段必须与翻转段的最后元素在翻转后的关系匹配。

这可以预处理每个位置向左的最长湍流长度（分最后是上升/下降），以及向右的最长湍流长度（分开始是上升/下降）。

步骤 8：预处理向左/向右的最长湍流长度（分方向）

我们已定义 up_left[i] 和 down_left[i] 为以 i 结尾，且最后上升/下降的长度。
类似定义 up_right[i] 和 down_right[i] 为以 i 开始，且开始上升/下降的长度。

注意：up_right[i] 表示从 i 开始，且 arr[i] < arr[i+1] 的情况下能延伸多长湍流（若 arr[i] > arr[i+1] 则 up_right[i]=1）。
因此：

if arr[i] < arr[i+1]:
    up_right[i] = down_right[i+1] + 1
else:
    up_right[i] = 1

if arr[i] > arr[i+1]:
    down_right[i] = up_right[i+1] + 1
else:
    down_right[i] = 1

初始化 up_right[n-1] = down_right[n-1] = 1，从右往左递推。

步骤 9：枚举翻转段的两个端点

我们考虑翻转段 [l, r] 在翻转后成为新数组中的一段连续子数组。
翻转段内部在原数组中的关系是反向的，所以翻转段内部在原数组中是“反向湍流”，即原来相邻比较关系交替，但方向与我们期望的相反。

因此，我们可以预处理原数组中每个位置开始的最长反向湍流长度（即把 < 和 > 互换后的湍流）。

更简单做法：我们枚举翻转段的左端点 l，然后尝试扩展右端点 r，同时维护翻转段内部在原数组中是反向湍流。
同时，我们需要检查翻转段两端与外部延伸的兼容性。

步骤 10：兼容性条件

假设翻转段为 [l, r]：

左延伸段：原数组中 l-1 到 l 的关系是 rel_left（< 或 >）。翻转后，l-1 与 l 的关系变为 arr[l-1] 与 arr[r] 的关系（因为 l 位置现在放的是原 arr[r]）。我们需要这个关系与左延伸段的最后方向匹配。
右延伸段：原数组中 r 到 r+1 的关系是 rel_right。翻转后，r 位置放的是原 arr[l]，所以 arr'[r] 与 arr[r+1] 的关系是原 arr[l] 与 arr[r+1] 的关系，需要与右延伸段的开始方向匹配。

因此，我们需要对每个可能的 (l, r) 检查这两个条件，并计算总长度。

步骤 11：优化枚举

我们可以只枚举 l，然后让 r 尽可能延伸，只要 [l, r] 在原数组中是反向湍流。
反向湍流的判断：在原数组中，对 [l, r] 段，要求 arr[l] > arr[l+1]，arr[l+1] < arr[l+2]，... 交替（即开始是下降）。或者开始是上升？
实际上，翻转段内部在原数组中的方向必须一致（交替），但与外部连接时方向要适配。

为了简化，我们考虑两种情况：翻转段在原数组中的开始方向是上升还是下降。

步骤 12：算法步骤

预处理 up_left, down_left, up_right, down_right。
初始化答案为无翻转的最长湍流长度。
枚举翻转段的左端点 l 从 0 到 n-1：
- 设 r = l 开始。
- 扩展 r 使得 [l, r] 在原数组中满足湍流交替条件（这是原方向，翻转后方向会反过来，但我们只关心长度）。
- 对于每个 r，检查：
  a) 如果 l > 0，则左边界：原 arr[l-1] 与 arr[r] 的关系必须匹配 left_ending_type（即 up_left[l-1] 或 down_left[l-1] 的方向）。
  b) 如果 r < n-1，则右边界：原 arr[l] 与 arr[r+1] 的关系必须匹配 right_starting_type（即 up_right[r+1] 或 down_right[r+1] 的方向）。
- 总长度 = 左延伸长度 + (r-l+1) + 右延伸长度。
- 更新答案。
返回答案。

步骤 13：举例说明

以 arr = [9,4,2,10,7,8,8,1,9] 为例：

无翻转最长湍流长度是 5（如 [4,2,10,7,8]）。
翻转 [7,8,8,1]（索引 4 到 7）变为 [1,8,8,7]，原数组此段是 [7,8,8,1]，翻转后 [1,8,8,7]。
翻转后整体数组：[9,4,2,10,1,8,8,7,9]。
寻找湍流子数组：从 2 开始：2<10>1<8>8>7<9？注意 8>7<9 是交替的，但 1<8>8 中 8>8？不对，8==8 会中断。所以需仔细找。

实际上，翻转 [7,8,8,1] 后，10,1,8,8,7 这一段：10>1<8>8>7 在 8>8 处相等，中断。所以不是更好。

我们需要按上述算法枚举所有可能翻转段。

步骤 14：时间复杂度

预处理 O(n)，枚举 l 和 r 扩展看似 O(n²)，但每个 l 扩展 r 时，由于湍流性质，r 只会右移 O(n) 次，所以总 O(n)。
实际可以用双指针维护以 l 开始的最长反向湍流段。

步骤 15：最终算法总结

预处理四个方向数组。
双指针找所有极长的湍流段（正反方向都找）。
对于每个可能的翻转段 [l, r]（即原数组中的一个湍流段，但方向与期望相反），计算拼接左右可能延伸的长度。
答案为所有情况最大值。

这样我们就能在 O(n) 时间内求出最多翻转一个子数组后的最长湍流子数组长度。

最长湍流子数组的变种——最多允许翻转一个子数组的最长湍流子数组题目描述给定一个整数数组 arr ，如果比较符号在数组中每个相邻元素对之间翻转（即 arr[i] < arr[i+1] 且 arr[i+1] > arr[i+2] ，或者 arr[i] > arr[i+1] 且 arr[i+1] < arr[i+2] ），则该子数组被称为“湍流子数组”。你可以至多翻转任意一个子数组一次（即将该子数组内的所有元素反转顺序），然后返回翻转后可能得到的最长湍流子数组的长度。示例：输入： arr = [9,4,2,10,7,8,8,1,9] 解释：如果不翻转，最长湍流子数组为 [4,2,10,7,8] 或 [2,10,7,8] ，长度为 5。但翻转某个子数组可能得到更长的湍流子数组。例如翻转子数组 [8,8] （实际上翻转后仍是 [8,8] ），无法延长；若翻转 [7,8,8,1] 为 [1,8,8,7] ，则可得到更长的湍流子数组 [10,7,1,8,8,7] ？我们需系统计算。实际上，该示例中翻转一个子数组可能得到更长湍流子数组，本题目标就是求出这个最大长度。解题过程循序渐进讲解步骤 1：理解湍流子数组定义湍流子数组要求相邻元素之间的比较关系交替变化：如果 arr[i] < arr[i+1] ，则下一个关系应为 arr[i+1] > arr[i+2] （即 > ），再下一个为 < ，以此类推。另一种可能是从 > 开始交替。长度为 1 的子数组视为湍流（因为没有相邻比较）。长度为 2 的子数组，只要两元素不等（ < 或 > ），也算湍流。但题目通常定义湍流需至少三个元素才要求交替，我们这里按 LeetCode 978 原题定义：对于长度 ≥2 的子数组，只要相邻比较符号交替即可；若相邻元素相等，则湍流中断。步骤 2：先解决无翻转的情况（LeetCode 978 原题）我们用两个动态规划数组： up[i] ：以 i 结尾，且最后一段比较是上升（ arr[i-1] < arr[i] ）的最长湍流子数组长度。 down[i] ：以 i 结尾，且最后一段比较是下降（ arr[i-1] > arr[i] ）的最长湍流子数组长度。转移方程：如果 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 。最终答案是所有 max(up[i], down[i]) 的最大值。这样我们能在 O(n) 时间求出无翻转的最长湍流子数组长度。步骤 3：考虑翻转一个子数组的影响翻转一个子数组 [l, r] 后，该子数组内的相邻比较关系全部反向（原来 < 变成 > ，原来 > 变成 < ，相等不变）。翻转后，原数组被分成三部分：前缀 [0, l-1] ：不变。翻转段 [l, r] ：内部相邻关系反向。后缀 [r+1, n-1] ：不变。我们需要计算翻转后，跨越这三部分的某个湍流子数组的最大长度。步骤 4：关键观察翻转后，湍流子数组可能：完全位于前缀内部（无影响）。完全位于翻转段内部（相当于原翻转段内部反向后的湍流长度）。完全位于后缀内部（无影响）。跨越前缀与翻转段的边界。跨越翻转段与后缀的边界。同时跨越前缀、翻转段、后缀。但注意：翻转段内部反向，会影响边界处的比较关系方向连续性。因此，我们需要预处理四个数组，以便快速得到翻转后的湍流长度。步骤 5：预处理数组定义： up_left[i] ：以 i 结尾，且最后比较为上升 ( arr[i-1] < arr[i] ) 的湍流子数组长度（从左边正常计算，即 up[i] ）。 down_left[i] ：以 i 结尾，且最后比较为下降的湍流子数组长度（即 down[i] ）。 up_right[i] ：以 i 开头，且第一段比较为上升 ( arr[i] < arr[i+1] ) 的湍流子数组长度（向右延伸）。 down_right[i] ：以 i 开头，且第一段比较为下降 ( arr[i] > arr[i+1] ) 的湍流子数组长度。如何求 up_right 和 down_right ？我们可以从右向左 DP：设 up_right[i] 为从 i 开始向右，满足第一段比较为上升的最长湍流长度。如果 arr[i] < arr[i+1] ，则 up_right[i] = down_right[i+1] + 1 ；如果 arr[i] > arr[i+1] ，则 down_right[i] = up_right[i+1] + 1 ；如果相等，则 up_right[i] = down_right[i] = 1 。注意： up_right[i] 必须满足第一段是上升，所以如果 arr[i] > arr[i+1] ，则 up_right[i] = 1 。类似地定义 down_right[i] 。更简单的办法：把数组反转后，用 up_left 的逻辑求，再映射回来。但直接推导更直观。步骤 6：翻转一个子数组 [l, r] 后的最长湍流计算设翻转后数组为 arr' 。在 arr' 中，对于位置 i 和 i+1 ：如果 i 和 i+1 都在翻转段内，则比较关系反向。如果 i 在翻转段内， i+1 在翻转段外，则比较关系取决于原数组的 arr[i] 和 arr[i+1] 的反向？不对，边界处：翻转段 [l, r] ，考虑 l-1 与 l （边界）：在原数组中 arr[l-1] 与 arr[l] 的关系是某个方向。翻转后， arr'[l-1] = arr[l-1] ， arr'[l] = arr[r] （因为翻转段反转了，原来 l 位置变成了 arr[r] ）。所以边界关系改变，不能简单用预处理数组。因此，更稳健的方法是：枚举所有可能的湍流子数组的起点和终点，检查是否可以通过一次翻转得到，但这样是 O(n²)，太慢。我们需要 O(n) 或 O(n log n) 的方法。步骤 7：高效算法思路考虑翻转后，湍流子数组必定由三部分组成（可能某些部分长度为 0）：一个从某个点向左延伸的湍流段（在原数组中正常方向）。中间一段是翻转段的一部分，且其内部在原数组中反向看也是湍流。一个从某个点向右延伸的湍流段（在原数组中正常方向）。关键在于：如果我们固定中间翻转段的两个端点 l 和 r ，那么：左延伸段必须与翻转段的第一元素在翻转后的关系匹配。右延伸段必须与翻转段的最后元素在翻转后的关系匹配。这可以预处理每个位置向左的最长湍流长度（分最后是上升/下降），以及向右的最长湍流长度（分开始是上升/下降）。步骤 8：预处理向左/向右的最长湍流长度（分方向）我们已定义 up_left[i] 和 down_left[i] 为以 i 结尾，且最后上升/下降的长度。类似定义 up_right[i] 和 down_right[i] 为以 i 开始，且开始上升/下降的长度。注意： up_right[i] 表示从 i 开始，且 arr[i] < arr[i+1] 的情况下能延伸多长湍流（若 arr[i] > arr[i+1] 则 up_right[i]=1 ）。因此：初始化 up_right[n-1] = down_right[n-1] = 1 ，从右往左递推。步骤 9：枚举翻转段的两个端点我们考虑翻转段 [l, r] 在翻转后成为新数组中的一段连续子数组。翻转段内部在原数组中的关系是反向的，所以翻转段内部在原数组中是“反向湍流”，即原来相邻比较关系交替，但方向与我们期望的相反。因此，我们可以预处理原数组中每个位置开始的最长反向湍流长度（即把 < 和 > 互换后的湍流）。更简单做法：我们枚举翻转段的左端点 l ，然后尝试扩展右端点 r ，同时维护翻转段内部在原数组中是反向湍流。同时，我们需要检查翻转段两端与外部延伸的兼容性。步骤 10：兼容性条件假设翻转段为 [l, r] ：左延伸段：原数组中 l-1 到 l 的关系是 rel_left （ < 或 > ）。翻转后， l-1 与 l 的关系变为 arr[l-1] 与 arr[r] 的关系（因为 l 位置现在放的是原 arr[r] ）。我们需要这个关系与左延伸段的最后方向匹配。右延伸段：原数组中 r 到 r+1 的关系是 rel_right 。翻转后， r 位置放的是原 arr[l] ，所以 arr'[r] 与 arr[r+1] 的关系是原 arr[l] 与 arr[r+1] 的关系，需要与右延伸段的开始方向匹配。因此，我们需要对每个可能的 (l, r) 检查这两个条件，并计算总长度。步骤 11：优化枚举我们可以只枚举 l ，然后让 r 尽可能延伸，只要 [l, r] 在原数组中是反向湍流。反向湍流的判断：在原数组中，对 [l, r] 段，要求 arr[l] > arr[l+1] ， arr[l+1] < arr[l+2] ，... 交替（即开始是下降）。或者开始是上升？实际上，翻转段内部在原数组中的方向必须一致（交替），但与外部连接时方向要适配。为了简化，我们考虑两种情况：翻转段在原数组中的开始方向是上升还是下降。步骤 12：算法步骤预处理 up_left , down_left , up_right , down_right 。初始化答案为无翻转的最长湍流长度。枚举翻转段的左端点 l 从 0 到 n-1：设 r = l 开始。扩展 r 使得 [l, r] 在原数组中满足湍流交替条件（这是原方向，翻转后方向会反过来，但我们只关心长度）。对于每个 r ，检查： a) 如果 l > 0 ，则左边界：原 arr[l-1] 与 arr[r] 的关系必须匹配 left_ending_type （即 up_left[l-1] 或 down_left[l-1] 的方向）。 b) 如果 r < n-1 ，则右边界：原 arr[l] 与 arr[r+1] 的关系必须匹配 right_starting_type （即 up_right[r+1] 或 down_right[r+1] 的方向）。总长度 = 左延伸长度 + (r-l+1) + 右延伸长度。更新答案。返回答案。步骤 13：举例说明以 arr = [9,4,2,10,7,8,8,1,9] 为例：无翻转最长湍流长度是 5（如 [4,2,10,7,8] ）。翻转 [7,8,8,1] （索引 4 到 7）变为 [1,8,8,7] ，原数组此段是 [7,8,8,1] ，翻转后 [1,8,8,7] 。翻转后整体数组： [9,4,2,10,1,8,8,7,9] 。寻找湍流子数组：从 2 开始： 2<10>1<8>8>7<9 ？注意 8>7<9 是交替的，但 1<8>8 中 8>8 ？不对， 8==8 会中断。所以需仔细找。实际上，翻转 [7,8,8,1] 后， 10,1,8,8,7 这一段： 10>1<8>8>7 在 8>8 处相等，中断。所以不是更好。我们需要按上述算法枚举所有可能翻转段。步骤 14：时间复杂度预处理 O(n)，枚举 l 和 r 扩展看似 O(n²)，但每个 l 扩展 r 时，由于湍流性质， r 只会右移 O(n) 次，所以总 O(n)。实际可以用双指针维护以 l 开始的最长反向湍流段。步骤 15：最终算法总结预处理四个方向数组。双指针找所有极长的湍流段（正反方向都找）。对于每个可能的翻转段 [l, r] （即原数组中的一个湍流段，但方向与期望相反），计算拼接左右可能延伸的长度。答案为所有情况最大值。这样我们就能在 O(n) 时间内求出最多翻转一个子数组后的最长湍流子数组长度。