Grimoire

# 978. 最长湍流子数组

# 题目

当 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 的最大湍流子数组的长度。

例

输入：[9,4,2,10,7,8,8,1,9]

输出：5

解释：(A[1] > A[2] < A[3] > A[4] < A[5])

# 题解

# 滑动窗口

设数组 arr 的长度为 n，窗口 [left,right](0≤left≤right≤n−1) 为当前的窗口，窗口内构成了一个「湍流子数组」。随后，我们要考虑下一个窗口的位置。

根据「湍流子数组」的定义，当 0<right<n−1 时：

如果 arr[right−1]<arr[right] 且 arr[right]>arr[right+1]，则 [left,right+1] 也构成「湍流子数组」，因此需要将 right 右移一个单位；

如果 arr[right−1]>arr[right] 且 arr[right]<arr[right+1]，同理，也需要将 right 右移一个单位；

否则，[right−1,right+1] 无法构成「湍流子数组」，当 left<right 时，[left,right+1] 也无法构成「湍流子数组」，因此需要将 left 移到 right，即令 left=right。

此外，我们还需要特殊考虑窗口长度为 1 (即 left 和 right 相等的情况)：只要 arr[right]!=arr[right+1]，就可以将 right 右移一个单位；否则，left 和 right 都要同时右移。

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxTurbulenceSize = function(arr) {
  const n = arr.length;
  let ret = 1;
  let left = 0,
    right = 0;

  while (right < n - 1) {
    if (left == right) {
      if (arr[left] == arr[left + 1]) {
        left++;
      }
      right++;
    } else {
      if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
        right++;
      } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
        right++;
      } else {
        left = right;
      }
    }
    ret = Math.max(ret, right - left + 1);
  }
  return ret;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度：O(n)，其中 n 为数组的长度。窗口的左右端点最多各移动 n 次。 空间复杂度：O(1)。只需要维护常数额外空间。

# 动态规划

记 dp[i][0] 为以 arr[i] 结尾，且 arr[i−1]>arr[i] 的「湍流子数组」的最大长度；dp[i][1] 为以 arr[i] 结尾，且 arr[i−1]<arr[i] 的「湍流子数组」的最大长度。

显然，以下标 0 结尾的「湍流子数组」的最大长度为 1，因此边界情况为 dp[0][0]=dp[0][1]=1。

当 i>0 时，考虑 arr[i−1] 和 arr[i] 之间的大小关系：

  • arr[i−1]==arr[i] 时 dp[i][0] = dp[i][1] = 1
  • arr[i-1]>arr[i] 时 dp[i][0] = dp[i-1][1]+1 dp[i][0]=1
    • dp[i-1][1] => arr[i-2]<arr[i-1]
    • dp[i][0] => arr[i-1]>arr[i]
    • 下面情况同理
  • arr[i-1]<arr[i] 时 dp[i][1] = dp[i-1][0]+1 dp[i][1]=1
/**
 * @param {number[]} arr
 * @return {number}
 */
var maxTurbulenceSize = function(arr) {
  const n = arr.length;
  let res = 1;
  let d0 = (d1 = 1);
  for (let i = 1; i < n; ++i) {
    if (arr[i - 1] > arr[i]) {
      d0 = d1 + 1;
      d1 = 1;
    } else if (arr[i - 1] < arr[i]) {
      d1 = d0 + 1;
      d0 = 1;
    } else {
      d1 = d0 = 1;
    }
    res = Math.max(res, d0, d1);
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：O(n)，其中 n 为数组的长度。 空间复杂度：O(1)。只需要维护常数额外空间。

← 1004. 最大连续 1 的个数 III →