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

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[i1], ..., A[j] 满足下列条件时我们称其为湍流子数组若 i k j当 k 为奇数时A[k] A[k1]且当 k 为偶数时A[k] A[k1] 或若 i k j当 k 为偶数时A[k] A[k1]且当 k 为奇数时A[k] A[k1]。也就是说如果比较符号在子数组中的每个相邻元素对之间翻转则该子数组是湍流子数组。返回 A 的最大湍流子数组的长度。直白地翻译子数组内相邻两两比较符号必须交替—— 或 不允许出现或的连续相同方向尤其不允许出现相等相等元素既不算大于也不算小于必然打断交替。三个官方示例输入输出说明[9,4,2,10,7,8,8,1,9]5(A[1] A[2] A[3] A[4] A[5])即4 2 10 7 8[4,8,12,16]2单调递增只有任意相邻一对满足长度为 2[100]1单元素数组任何单个元素本身即为湍流子数组数据范围约束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就应第一时间联想到滑动窗口。两种基本类型固定窗口大小左右指针同时移动窗口长度恒定可变窗口大小本题属于此类l和r都初始化为 0r指针不停右移扩张窗口l指针仅在窗口条件被破坏时才右移收缩每次扩张后更新最优解。该专题还给出了通用模板伪代码初始化慢指针 0 初始化 ans for 快指针 in 可迭代集合 更新窗口内信息 while 窗口内不符合题意 扩展或者收缩窗口 慢指针移动 更新答案 返回 ans978 正是窗口大小不固定、求解满足条件的最大窗口这一子类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 ans4.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]每轮差值符号相同 ^ 0i j - 1窗口长度恒为 2返回 2与示例 2 一致。五、复杂度分析与总结时间复杂度$O(N)$单次遍历i、j各自最多移动 N 次均摊线性空间复杂度$O(1)$仅使用常数个变量无需显式构造符号数组符号判断即时计算符合原题对内存的极致要求。本题的完整解题链路可以概括为一条可复用的思维管线识别连续问题看到最长湍流子数组连续联想到 thinkings/slide-window.md 中的可变窗口套路差分符号化把相邻比较关系投影为 / - / 0符号序列将交替翻转翻译为符号序列正负相间找断裂条件相邻相等0与同号未翻转是两个明确的窗口收缩触发器符号判断防溢出用a ^ b 0代替a * b 0长度换算符号段长度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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考