LeetCode 题解工作台
最长湍流子数组
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的 长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。 更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为 湍流子数组 ： 若 i ： 当…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示以 结尾且结尾处于上升状态的最长湍流子数组的长度，定义 表示以 结尾且结尾处于下降状态的最长湍流子数组的长度。初始时 $f[0] = 1$, $g[0] = 1$。答案为 $\max(f[i], g[i])$。 对于 $i \gt 0$，若 $\textit{nums}[i] \gt \textit{nums}[i - 1]$，则 $f[i] = g[i - 1] + 1$，…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
- 若
i <= k < j：- 当
k为奇数时，A[k] > A[k+1]，且 - 当
k为偶数时，A[k] < A[k+1]；
- 当
- 或 若
i <= k < j：- 当
k为偶数时，A[k] > A[k+1]，且 - 当
k为奇数时，A[k] < A[k+1]。
- 当
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9] 输出：5 解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16] 输出：2
示例 3：
输入：arr = [100] 输出：1
提示：
1 <= arr.length <= 4 * 1040 <= arr[i] <= 109
解题思路
方法一：动态规划
我们定义 表示以 结尾且结尾处于上升状态的最长湍流子数组的长度，定义 表示以 结尾且结尾处于下降状态的最长湍流子数组的长度。初始时 , 。答案为 。
对于 ，若 ，则 ，否则 ；若 ，则 ，否则 。
由于 和 只与 和 有关，因此可以使用两个变量代替数组。
时间复杂度 ，其中 为数组长度。空间复杂度 。
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
ans = f = g = 1
for a, b in pairwise(arr):
ff = g + 1 if a < b else 1
gg = f + 1 if a > b else 1
f, g = ff, gg
ans = max(ans, f, g)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Focus on edge cases like repeated values or single-element arrays.
- question_mark
Expect clarification on handling the first element comparison and index parity.
- question_mark
Consider discussing the trade-off between sliding window and explicit DP arrays.
常见陷阱
外企场景- error
Failing to reset state when consecutive elements are equal, leading to incorrect subarray length.
- error
Confusing index parity with comparison direction, breaking the turbulence check.
- error
Using O(N^2) nested loops instead of linear state tracking, which is inefficient for large arrays.
进阶变体
外企场景- arrow_right_alt
Return the actual subarray instead of just its length, requiring backtracking of start and end indices.
- arrow_right_alt
Compute turbulent subarrays on a 2D grid flattened row-wise, combining row and column alternations.
- arrow_right_alt
Find maximum turbulent segments where only '>' alternates with '<=' instead of strict '<', changing state transitions slightly.