企业官网建设流程全解析

LeetCode-Go 题解 978：最长湍流子数组（Longest Turbulent Subarray）的滑动窗口与双状态 DP 实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 978 题Longest Turbulent Subarray（最长湍流子数组），以仓库中 leetcode/0978.Longest-Turbulent-Subarray/README.md 为核心骨架，结合同目录下的两份 Go 源码展开讲解。读完本文，你将掌握“湍流子数组”的精确定义、两种 O(n) 时间 / O(1) 空间的解法（滑动窗口与双状态模拟/DP），并能理解源码中利用位运算 XOR 判断符号翻转的巧妙技巧，以及仓库测试用例的边界覆盖情况。

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

原文档给出了严格的数学定义。对于数组A的任意子数组A[i], A[i+1], ..., A[j]，当且仅当满足下列条件之一时，它被称为湍流子数组（turbulent subarray）：

• 对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. 1 <= A.length <= 40000
2. 0 <= A[i] <= 10^9

n最大可达 4 万，意味着 O(n²) 的暴力枚举必然超时，必须在单次线性扫描（配合常数空间）内解决问题——这正是仓库中两个解法的时间复杂度定位。

解法一：滑动窗口（README 推荐思路）

原文档的“解题思路”一节明确指出：这一题可以用滑动窗口来解答，并用“相邻元素差的乘积大于零（a ^ b >= 0说明 a、b 乘积大于零）来判断是否是湍流：如果是，扩大窗口；否则窗口缩小，开始新窗口”。

仓库中的实现位于 978. Longest Turbulent Subarray.go 的maxTurbulenceSize1：

// 解法二 滑动窗口 func maxTurbulenceSize1(arr []int) int { var maxLength int if len(arr) == 2 && arr[0] != arr[1] { maxLength = 2 } else { maxLength = 1 } left := 0 for right := 2; right < len(arr); right++ { if arr[right] == arr[right-1] { left = right } else if (arr[right]-arr[right-1])^(arr[right-1]-arr[right-2]) >= 0 { left = right - 1 } maxLength = max(maxLength, right-left+1) } return maxLength }

位运算 XOR 判符号的技巧

这是本解法最值得深挖的一处。设相邻两段差值为：

• a = arr[right] - arr[right-1]（最新的一段差）
• b = arr[right-1] - arr[right-2]（前一段差）

湍流要求符号翻转，即a与b异号。源码用a ^ b >= 0作为湍流被破坏（同号）的判定条件，其原理是：

• 在补码表示下，两个同号（同为负或同为正）的整数最高位（符号位）相同，异或后最高位为 0，结果>= 0；
• 两个异号的整数符号位不同，异或后最高位为 1，结果< 0。

因此a ^ b >= 0等价于“a、b乘积非负”（即同号），这与原文档中“乘积大于零”的直觉一致，但用 XOR 实现避免了乘法可能带来的溢出顾虑，是纯位运算层面的优化。

三种情况分别如何收缩窗口

窗口[left, right]的维护逻辑清晰对应三种相邻关系：

1. arr[right] == arr[right-1]（最新一段差为 0）：相等元素直接打破湍流，窗口重置为left = right，新窗口从当前元素重新开始。
2. a ^ b >= 0（两段差同号，未发生翻转）：湍流在right-1处断裂，新窗口只能保留最后两个元素[right-1, right]，即left = right - 1。
3. 否则（异号，符号正常翻转）：left不动，窗口继续向右扩大。

每次迭代后用right - left + 1更新maxLength，最终即最大湍流子数组长度。

初始化的细节

由于循环从right = 2开始，长度为 2 的窗口需要单独初始化：若len(arr) == 2且两元素不相等，则maxLength = 2，否则为 1。这也保证了该解法在常规输入下能得到正确基线值。测试源码中特别注释说明，maxTurbulenceSize1对len(arr) < 2的输入（如空数组）处理与解法一不完全一致，因此测试仅对长度>= 2的用例做严格断言，这一点在“测试验证”一节会再展开。

解法二：模拟法 / 双状态 DP（仓库源码补充）

仓库在同一个源文件中还提供了解法一（maxTurbulenceSize），文件头注释将其命名为“模拟法”。本质上这是一个只依赖前一个状态的双变量动态规划：

// 解法一 模拟法 func maxTurbulenceSize(arr []int) int { inc, dec := 1, 1 maxLen := min(1, len(arr)) for i := 1; i < len(arr); i++ { if arr[i-1] < arr[i] { inc = dec + 1 dec = 1 } else if arr[i-1] > arr[i] { dec = inc + 1 inc = 1 } else { inc = 1 dec = 1 } maxLen = max(maxLen, max(inc, dec)) } return maxLen } func max(a int, b int) int { if a > b { return a } return b } func min(a int, b int) int { if a > b { return b } return a }

状态语义：inc 与 dec

定义两个状态变量，均表示“以当前位置i结尾的湍流子数组长度”：

• inc：最后一段比较关系为arr[i-1] < arr[i]（结尾是上升）的最大湍流长度；
• dec：最后一段比较关系为arr[i-1] > arr[i]（结尾是下降）的最大湍流长度。

由于湍流要求符号交替，推导规则为：

• 当前上升（arr[i-1] < arr[i]）：它必须接在“结尾为下降”的子数组后面，故inc = dec + 1；同时以“下降”结尾的状态被中断，dec = 1。
• 当前下降（arr[i-1] > arr[i]）：对称地，dec = inc + 1，且inc = 1。
• 当前相等（arr[i-1] == arr[i]）：湍流被破坏，两个状态都重置为 1。

空数组与单元素的兜底

maxLen := min(1, len(arr))是一个精心设计的兜底：

• 空数组：min(1, 0) = 0，正确返回 0；
• 非空数组：min(1, len(arr)) = 1，保证单元素输入直接得到 1，无需进入循环。

由于每个元素只扫描一次且仅维护两个常量状态，从源码结构可以确认，两个解法的时空复杂度均为O(n) 时间、O(1) 空间，完全适配n <= 40000的约束。

两种解法的对比

两者在正常输入（长度>= 2）下输出完全一致，测试代码对两种实现做了交叉校验。

测试用例验证

仓库测试文件 978. Longest Turbulent Subarray_test.go 采用了“参数 + 期望答案”的结构化表驱动测试，共覆盖 7 组用例：

测试中还通过t.Fatalf对解法一逐用例断言；对解法二，由于其对len < 2输入的语义差异（见源码注释），仅对长度>= 2的用例做严格比对，其余只调用不断言，体现了对实现差异的诚实处理。

若本机已安装 Go 工具链，可在仓库根目录按 gotest.sh 所示方式运行全部题解测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

或仅针对本题：

go test -v ./leetcode/0978.Longest-Turbulent-Subarray/

小结

本题的核心是识别“相邻比较符号必须交替”这一结构性约束。仓库给出的两条实现路线各有侧重：滑动窗口方案紧扣原文档思路，以 XOR 位运算优雅地完成同号判定；双状态模拟方案则以inc/dec转移清晰地刻画了符号翻转的递推关系。两者同为 O(n)/O(1)，配合覆盖空数组、等值元素、单调序列等边界的表驱动测试，是学习“最长湍流/摆动子数组”类问题的高质量参考实现。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go