企业官网建设流程全解析

LeetCode 978 最长湍流子数组（Longest Turbulent Subarray）：符号差分数组 + 滑动窗口 O(N) 解法实战解析

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本篇基于开源仓库「leetcode 题解，记录自己的 leetcode 解题之路」中的 978.longest-turbulent-subarray.md 题解文档展开，深入讲解 LeetCode 978「最长湍流子数组」的完整解题路径。你将掌握如何把"相邻元素比较符号交替翻转"这一看似绕口的条件，转化为差分符号数组 + 滑动窗口求最长区间的经典模型，学会使用异或运算在避免大数溢出的前提下判断符号是否相同，并理解本题与仓库中 3、209、1004、1658 等滑动窗口题型的家族关系。读完后，你能独立写出时间 O(N)、空间 O(1) 的 Python 解法，并具备将任意"连续区间满足交替条件"类问题归约到滑动窗口的能力。

一、题目定义：什么是"湍流子数组"

原题描述如下（完整保留自 problems/978.longest-turbulent-subarray.md）：

当 A 的子数组 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]。

也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。返回 A 的最大湍流子数组的长度。

直白地翻译：子数组内相邻两两比较，符号必须交替——> < > <或< > < >，不允许出现>=或<=的连续相同方向，尤其不允许出现相等（相等元素既不算大于也不算小于，必然打断交替）。

三个官方示例

数据范围约束

• 1 <= A.length <= 40000：规模允许 O(N log N)，但滑动窗口可做到 O(N)；
• 0 <= A[i] <= 10^9：差值可能接近 10^9 量级，相乘判断符号可能溢出，这正是原题解采用异或技巧的动机（见第四节）。

二、前置知识：滑动窗口（Sliding Window）

本题在仓库中被归类为滑动窗口题型，前置知识指向 thinkings/slide-window.md。该专题文档给出了滑动窗口的完整方法论：

• 核心思想：滑动窗口是一种解决"连续问题"的思路，凡题目要求"连续子串 xxxx / 连续子数组 xxxx"，就应第一时间联想到滑动窗口。
• 两种基本类型：
  1. 固定窗口大小：左右指针同时移动，窗口长度恒定；
  2. 可变窗口大小（本题属于此类）：l和r都初始化为 0，r指针不停右移扩张窗口，l指针仅在窗口条件被破坏时才右移收缩，每次扩张后更新最优解。

该专题还给出了通用模板（伪代码）：

初始化慢指针 = 0 初始化 ans for 快指针 in 可迭代集合 更新窗口内信息 while 窗口内不符合题意 扩展或者收缩窗口 慢指针移动 更新答案 返回 ans

978 正是"窗口大小不固定、求解满足条件的最大窗口"这一子类：r每步右移一位，若新元素破坏了"湍流交替"性质，就把l收缩到能重新满足条件的边界，然后ans = max(ans, j - i + 1)持续更新。

三、核心思路：把数组转成"差分符号数组"

3.1 符号数组的构造

对原题第一个例子A = [9,4,2,10,7,8,8,1,9]，构造数组arr，其中arr[i]表示A[i] - A[i-1]的符号：

• +表示A[i] > A[i-1]（差为正）；
• -表示A[i] < A[i-1]（差为负）；
• 0表示A[i] == A[i-1]（差为零）。

于是得到：

A = [9, 4, 2, 10, 7, 8, 8, 1, 9] arr = [ -, -, +, -, +, 0, -, + ] （长度恒为 A 的长度 - 1）

其余两个例子的符号数组分别是：

• [4,8,12,16]→[+, +, +]
• [100]→[]（单元素没有相邻对，符号数组为空）

3.2 问题归约：正负相间的最大长度

观察符号数组后不难发现，题目要求的湍流子数组，等价于符号数组中最长的一段"正负交替"区间。三个例子中答案部分如下（原题解用粗体标注）：

• [-, **-, +, -, +**, 0, -, +]：交替段长度为 4，对应原数组长度为4 + 1 = 5；
• [**+**, +, +]：最长交替段只有 1，对应原数组长度1 + 1 = 2；
• []：没有相邻对，交替段长度为 0，对应原数组长度0 + 1 = 1。

规律：符号数组中长度为k的交替段，映射回原数组就是长度为k + 1的湍流子数组。因此原题求"最大湍流子数组长度"被转化为"符号数组中最长正负交替段长度 + 1"。

从源码结构看，这个"连续 xx → 滑动窗口"的敏感性是仓库滑动窗口专题反复强调的套路，同一家族还包括：

• 3. 无重复字符的最长子串（哈希表 + 可变窗口）；
• 209. 长度最小的子数组（窗口和 ≥ s 时收缩取最小，是可变窗口的模板题）；
• 1004. 最大连续 1 的个数 III（允许翻转 K 个 0 的变长窗口）；
• 1658. 将 x 减到 0 的最小操作数（从两侧移除，等价于找中间最长连续段）。

四、代码实现与关键技巧

4.1 滑动窗口解法（Python）

原题解给出的代码如下：

class Solution: def maxTurbulenceSize(self, A: List[int]) -> int: ans = 1 i = 0 for j in range(2, len(A)): if (A[j] == A[j - 1]): i = j elif (A[j] - A[j - 1]) ^ (A[j - 1] - A[j - 2]) >= 0: i = j - 1 ans = max(ans, j - i + 1) return ans

4.2 逐行拆解

• ans = 1：初始化答案。因为任意单个元素都是长度为 1 的湍流子数组（对应示例 3），这是所有情况的下界；for j in range(2, len(A))从j = 2开始，因为判断交替至少需要考察A[j-2]、A[j-1]、A[j]三个元素。
• 分支一：A[j] == A[j - 1]：相邻相等。差值符号为 0，任何包含这一对的区间都不可能交替，因此窗口左边界直接跳到i = j，从当前元素重新开始。
• 分支二：(A[j] - A[j-1]) ^ (A[j-1] - A[j-2]) >= 0：说明相邻两段差值的符号相同（同为非负或同为非正），即没有发生翻转，交替在此处断裂。此时"以 j-1 结尾"的这一段仍可保留（A[j-1]与前面的元素仍构成交替），所以左边界收缩为i = j - 1。
• ans = max(ans, j - i + 1)：每轮都用当前窗口长度更新全局最优解。j - i + 1就是"符号交替段长度 + 1"，与 3.2 节的归约结论完全一致。

4.3 关键技巧：用异或判断符号相同

代码中的a ^ b >= 0等价于"a、b 同号"，这与常见的a * b > 0语义相同，但优势在于：

• 乘法在A[i]接近10^9、差值可达10^9量级时，乘积可能达到10^18，超出部分语言整型的精确表示范围，产生溢出或精度问题；
• 异或是对符号位（最高位）逐位运算：同号时符号位相同，异或结果最高位为 0，数值非负；异号时符号位相反，异或结果最高位为 1，数值为负。^只关心符号位，与数值大小无关，天然免疫大数溢出。

这是一个可以在任何"比较两个差值的符号是否一致"场景复用的通用技巧。

4.4 边界情况验证

• len(A) == 1（如[100]）：循环体不执行，直接返回ans = 1，正确；
• 全相等数组（如[1,1,1]）：每轮都走A[j] == A[j-1]分支，i不断前移，窗口始终为 1，返回 1，符合预期（任意相邻相等对都打断交替）；
• 单调数组（如[4,8,12,16]）：每轮差值符号相同（+ ^ + >= 0），i = j - 1，窗口长度恒为 2，返回 2，与示例 2 一致。

五、复杂度分析与总结

• 时间复杂度：$O(N)$：单次遍历，i、j各自最多移动 N 次，均摊线性；
• 空间复杂度：$O(1)$：仅使用常数个变量，无需显式构造符号数组（符号判断即时计算），符合原题对内存的极致要求。

本题的完整解题链路可以概括为一条可复用的思维管线：

1. 识别连续问题：看到"最长湍流子数组（连续）"，联想到 thinkings/slide-window.md 中的可变窗口套路；
2. 差分符号化：把相邻比较关系投影为+ / - / 0符号序列，将"交替翻转"翻译为"符号序列正负相间"；
3. 找断裂条件：相邻相等（0）与同号（未翻转）是两个明确的窗口收缩触发器；
4. 符号判断防溢出：用a ^ b >= 0代替a * b > 0；
5. 长度换算：符号段长度k↔ 原数组长度k + 1，窗口宽度j - i + 1直接计入答案。

该文档收录于仓库 problems/ 目录，与 thinkings/slide-window.md 形成"题目—方法论"配套；类似的滑动窗口题解还可在 3.longest-substring-without-repeating-characters.md、209.minimum-size-subarray-sum.md、1004.max-consecutive-ones-iii.md、1658.minimum-operations-to-reduce-x-to-zero.md 中对照研读，巩固"连续最值 → 滑动窗口"这一高频考点。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode