LeetCode 978. 最长湍流子数组
目录
题目描述
题意分析
给一个整数数组
arr，求最长「湍流子数组」的长度。湍流的定义是：子数组内相邻元素的大小关系严格交替，即比较符号呈现<, >, <, >, ...或>, <, >, <, ...的模式。把定义翻译成可操作的形式：对子数组
arr[l..r]，要求每一对相邻元素都严格不等，且相邻两对的比较方向相反。等价说法是——任何一个内部元素都不能与它的两个邻居构成同向的大小关系，它要么是局部的波峰，要么是局部的波谷。有三处必须精确落实。第一，比较是严格的，
arr[i] == arr[i+1]会直接把子数组切断，因为「相等」既不是上升也不是下降，无法参与交替。第二，长度为 1 的子数组天然是湍流（没有相邻对，条件空真），所以答案下界是 1，而不是 0。第三，长度为 2 的子数组只要两元素不等就是湍流。约束里
n最大到 $4 \times 10^4$，$O(n^2)$ 枚举所有子数组约 16 亿次比较，超时；$O(n)$ 一次扫描是期望复杂度。同时注意题目关心的是子数组（连续）而不是子序列，这决定了可以用「以某个位置结尾」的线性 DP，而不必上 LIS 那套 $O(n \log n)$ 结构。边界方面：数组全部相等（如
[9,9,9]）时答案是 1；数组严格单调（如[1,2,3]）时答案是 2，因为只能取到相邻两个。这两个用例正好卡住「相等切断」和「同向切断」两条规则。
解法：DP（up/down 滚动更新）
核心思路
暴力做法是枚举左右端点，逐个验证交替性，$O(n^3)$；稍作优化可以固定左端点向右扩展并在破坏交替时停止，降到 $O(n^2)$。
n到 4 万时仍然超时。瓶颈在于反复重新验证同一段前缀的交替性。观察：湍流是一个局部可增量维护的性质——一段以
i结尾的湍流子数组能否再往右接上arr[i+1]，只取决于「这一段最后一对的比较方向」和「arr[i]与arr[i+1]的比较方向」是否相反。也就是说，只需要记住最后一步是升还是降，前面的细节全部可以丢掉。于是定义两个状态（都是「以下标
i结尾」的最长湍流长度）：
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；同时以i结尾且最后一步是下降的段不存在，down[i]只能取长度 1 的退化值。- 若
arr[i] < arr[i-1]（本步下降），对称地down[i] = up[i-1] + 1，up[i]重置为 1。- 若
arr[i] == arr[i-1]，交替被彻底切断，两个状态都重置为 1。这里把「重置为 1」而不是 0，是因为单个元素本身就是合法的湍流子数组，它是下一段的起点。这个约定让所有边界（数组开头、相等切断）统一，不需要任何特判。
维持的不变量是：处理完位置
i后，up与down分别等于以i结尾、最后一步为升/降的最长湍流长度，二者中至少有一个反映了真实可扩展的段，另一个为退化值 1。全局答案就是所有位置上max(up, down)的最大值。由于转移只依赖
i - 1这一层，可以直接用两个标量滚动，无需开数组，空间降到 $O(1)$。注意滚动时必须先用旧值算出新值再写回——up = down + 1这一行用到的down是上一轮的值，写完up之后才能把down重置，顺序反了就会用到本轮刚写的脏值。
解题步骤
- 初始化
up = down = 1，answer = 1：对应只看第一个元素时的状态。为什么答案初值是 1 而不是 0：单元素子数组本身合法，且数组长度至少为 1，若初值取 0 则[1]这类输入会返回错误的 0。- 从
i = 1开始遍历：状态转移需要arr[i-1]，所以第一个可比较的位置是 1。为什么不需要对n == 1特判：循环体一次都不执行，直接返回初值 1，正好正确。- 分支一：
arr[i] > arr[i-1]。先up = down + 1，再down = 1。为什么up接的是down：交替要求上一步必须是下降；接up就变成连续两次上升，违反定义。为什么down要归 1：以i结尾且最后一步是下降的段在本轮不存在，只能退化成单元素。为什么两行不能交换顺序：先写down = 1会让up = down + 1恒等于 2，把历史长度全部抹掉。- 分支二：
arr[i] < arr[i-1]。对称地down = up + 1，up = 1，理由与上一条镜像。- 分支三：相等。
up = down = 1。为什么必须单独处理：相等既不是升也不是降，任何跨过它的子数组都不可能是湍流，两个状态都要从头开始。若把它并进某个不等分支，会让相等对被当作一次有效交替，答案偏大。- 每轮更新全局答案：
answer = max(answer, max(up, down))。为什么要每轮更新而不是循环结束后再取：最长段可能结束在中间任何位置，只看末尾会漏。- 返回
answer。以
arr = [9,4,2,10,7,8,8,1,9]走一遍（预期答案 5）。初始up = down = 1，answer = 1。
i = 1（4 < 9，下降）：down = up + 1 = 2，up = 1。answer = 2。
i = 2（2 < 4，下降）：down = up + 1 = 2（上一轮up已被重置为 1，所以这里正确地重新起段），up = 1。answer = 2。
i = 3（10 > 2，上升）：up = down + 1 = 3，down = 1。answer = 3。对应子数组[2,10]之前还接着4，即[4,2,10]。
i = 4（7 < 10，下降）：down = up + 1 = 4，up = 1。answer = 4，对应[4,2,10,7]。
i = 5（8 > 7，上升）：up = down + 1 = 5，down = 1。answer = 5，对应[4,2,10,7,8]。
i = 6（8 == 8，相等）：up = down = 1。answer保持 5。这一步正是相等切断规则生效的地方。
i = 7（1 < 8，下降）：down = up + 1 = 2，up = 1。answer仍是 5。
i = 8（9 > 1，上升）：up = down + 1 = 3，down = 1。answer仍是 5。
返回 5，与预期一致。再看
arr = [4,8,12,16]：每一步都是上升，up = down + 1中的down始终是上一轮被重置的 1，所以up恒为 2，答案是 2——同向不能连续，这正是规则要求的。而arr = [100]循环不执行，返回 1。
代码实现
class Solution {
public int maxTurbulenceSize(int[] arr) {
// up/down：以当前位置结尾、最后一步为升/降的最长湍流长度。
int up = 1;
int down = 1;
int answer = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
// 本步上升，只能接在「上一步下降」的段后面。
up = down + 1;
down = 1;
} else if (arr[i] < arr[i - 1]) {
down = up + 1;
up = 1;
} else {
// 相等切断交替，两个状态都从单元素重新开始。
up = 1;
down = 1;
}
answer = Math.max(answer, Math.max(up, down));
}
return answer;
}
}
func maxTurbulenceSize(arr []int) int {
// up/down：以当前位置结尾、最后一步为升/降的最长湍流长度。
up, down := 1, 1
answer := 1
for i := 1; i < len(arr); i++ {
if arr[i] > arr[i-1] {
// 本步上升，只能接在「上一步下降」的段后面。
up = down + 1
down = 1
} else if arr[i] < arr[i-1] {
down = up + 1
up = 1
} else {
// 相等切断交替，两个状态都从单元素重新开始。
up, down = 1, 1
}
answer = max(answer, max(up, down))
}
return answer
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：只有一层从 1 到
n - 1的循环，循环体内是常数次比较、赋值与取最大值，没有任何嵌套或回退。- 空间复杂度：$O(1)$。凭什么：转移只依赖前一个位置的两个状态，用
up、down两个标量滚动即可，不需要长度为n的 DP 数组；输入数组本身不计入额外空间。
关键点总结
- 「以某个位置结尾」是连续子数组类 DP 的标准状态设计，它把「枚举左端点」的一维彻底消掉；配合最后再取全局最大值，能覆盖所有可能的结束位置。
- 当合法性依赖「上一步的方向」时，就该按方向拆成多个状态构成状态机。本题拆成升/降两个，152 题拆成最大/最小两个，思路完全一致。
- 滚动变量更新时务必确认「新值是否用到了同一轮的旧值」。
up = down + 1必须排在down = 1前面，顺序一反就用到脏值，这是本题最隐蔽的错误。- 状态重置成 1 而不是 0，是因为单元素本身合法。把「退化情形」设成合法起点，可以让开头、切断等边界统一走主逻辑，省掉全部特判。
- 严格不等的定义必须显式给相等留一个分支，不能让它落进任何一个不等分支——
>=与>的差别会直接改变答案。- 面试视角：面试官想听状态定义。开口说「
up[i]表示以i结尾且最后一对是上升的最长湍流长度」，转移式几乎自动成立；写完后主动举[9,9]和[1,2,3]两个用例说明相等切断与同向切断。若被追问，可以说这题也能用滑动窗口做（窗口内维护交替性，破坏时收缩左边界），但状态机 DP 更短、更不容易在收缩条件上出错。
易错点总结
- 错误写法：答案初始化为 0 → 用例
[100]循环体不执行，返回 0，而单元素子数组合法，正确答案是 1。- 错误写法：状态重置成 0 而不是 1 → 用例
[9,9,4]中相等切断后up与down都是 0，i = 2时down = up + 1 = 1，漏掉了[9,4]这段，答案从 2 变成 1。- 错误写法：把
down = 1写在up = down + 1之前 → 用例[9,4,2,10,7,8]中up恒等于 2，历史长度被抹掉，答案从 5 变成 2。- 错误写法：上升时写成
up = up + 1→ 用例[4,8,12,16]中连续上升被累加成 4，而同向不构成湍流，正确答案是 2。- 错误写法：比较用
>=与<=，不给相等留分支 → 用例[9,9,9]中相等被当成有效交替，答案变成 3，正确答案是 1。- 错误写法：只用
max(up, down)在循环结束后取一次 → 用例[9,4,2,10,7,8,8,1,9]中最长段在i = 5结束，末尾状态只有 3，返回 3 而不是 5。- 错误写法：循环从
i = 0开始并访问arr[i-1]→ 用例任意输入都会在首轮越界，Java 抛数组越界异常，Go 直接 panic。- 错误写法：只维护一个变量
len，靠记录上一次比较符号来判断是否延长 → 用例[9,9,4]中符号变量在相等时没有定义，逻辑分叉难以自洽；实际上这等价于把两个状态硬压成一个，遇到切断就会算错。- 错误写法：用滑动窗口但收缩时把左边界直接设为
i→ 用例[9,4,2,10]中i = 2处交替被破坏，左边界应设为i - 1（保留arr[i-1]作为新段起点），设成i会漏掉[2,10]这样的两元素段。- 错误写法：把题目理解成子序列而非子数组，套用 376 摆动序列的解法 → 用例
[9,4,2,10,7,8,8,1,9]会返回更长的摆动子序列长度，而本题要求元素连续。- 错误写法：认为答案至少为 2 并直接返回
max(answer, 2)→ 用例[9,9,9]中不存在任何长度 2 的湍流段，返回 2 是错的，正确答案是 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 同为「以 i 结尾」的线性 DP，但状态只有一个，转移靠与 0 比较取舍 |
| 152. 乘积最大子数组 | 中等 | 同样拆成两个滚动状态（最大/最小），拆分理由是负号翻转而非方向交替 |
| 674. 最长连续递增序列 | 简单 | 只要求单向递增，无需状态机，是本题去掉交替约束后的最简版本 |
| 376. 摆动序列 | 中等 | 交替规则相同但对象是子序列可跳元素，允许跳过使得贪心解法成立 |
| 300. 最长递增子序列 | 中等 | 子序列版本，状态转移需要回看所有更小结尾，$O(n \log n)$ 需配二分 |
| 845. 数组中的最长山脉 | 中等 | 也是连续段上的方向约束，但只允许「先升后降」一次转折而非反复交替 |
| 1567. 乘积为正数的最长子数组长度 | 中等 | 同样双状态滚动，状态区分的是正负号奇偶而不是升降方向 |