0978. 最长湍流子数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 滑动窗口

1. 📝 题目描述

• leetcode

给定一个整数数组 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 * 10^4
• 0 <= arr[i] <= 10^9

2. 🎯 s.1 - 滑动窗口

js

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxTurbulenceSize = function (arr) {
  const n = arr.length
  if (n <= 1) return n

  let maxLen = 1
  let len = 1 // 当前湍流子数组长度
  let prevCmp = 0 // 前一个比较结果：1表示>，-1表示<，0表示=

  for (let i = 1; i < n; i++) {
    const cmp = Math.sign(arr[i] - arr[i - 1])

    if (cmp === 0) {
      // 相等，重置长度
      len = 1
      prevCmp = 0
    } else if (prevCmp === 0 || prevCmp + cmp === 0) {
      // prevCmp === 0: 刚开始或刚重置
      // prevCmp + cmp === 0: 比较符号翻转（1 + (-1) = 0 或 -1 + 1 = 0）
      len++
      prevCmp = cmp
    } else {
      // 比较符号没有翻转，从当前位置重新开始
      len = 2
      prevCmp = cmp
    }

    maxLen = Math.max(maxLen, len)
  }

  return maxLen
}

• 时间复杂度：$O(n)$，其中 n 是数组长度，只需遍历一次数组
• 空间复杂度：$O(1)$，只使用常数级别的额外空间

算法思路：

• 状态维护：用 len 维护当前湍流子数组的长度，prevCmp 记录前一个比较结果（1表示>，-1表示<，0表示=）
• 比较符号：用 Math.sign(arr[i] - arr[i-1]) 计算当前比较结果
• 相等处理：如果相邻元素相等，湍流序列中断，重置长度为 1
• 符号翻转：如果比较符号翻转（prevCmp + cmp === 0），说明满足湍流条件，长度加 1
• 符号未翻转：如果比较符号未翻转，从当前位置重新开始计数，长度重置为 2（包含前一个元素和当前元素）
• 结果更新：每次迭代更新最大长度