978. 最长湍流子数组

给定一个整数数组 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：

1
2
3
输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

1
2
输入：arr = [4,8,12,16]
输出：2

示例 3：

1
2
输入：arr = [100]
输出：1

提示：

  • 1 <= arr.length <= 4 * 104
  • 0 <= arr[i] <= 109

解题思路：

湍流子数组的形成条件是两种相反的状态，所以需要两个dp数组来分别表示两种状态。

  1. 确定dp数组及其下标含义：
    1. 定义up[i]表示以位置i结尾，并且arr[i-1] < arr[i]的最长湍流子数组的长度
    2. 定义down[i]来表示以位置i结尾，，并且arr[i-1] >arr[i]的最长湍流子数组的长度
  2. 确定递推方程：
    1. 当arr[i - 1] < arr[i]，根据下降湍流子数组的长度更新上升数组，up[i] = down[i -1] + 1，并记录最大值
    2. 当arr[i - 1] > arr[i]，根据上升湍流子数组的长度更新上升数组，down[i] = up[i -1] + 1，并记录最大值
  3. dp数组如何初始化：
    1. 因为每个数字本身就是一个最小的湍流子数组，所以up[i]和down[i]初始化都为1

代码如下：

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
30
31
public int maxTurbulenceSize(int[] arr) {
    int length = arr.length;

    //用于记录最长湍流子数组长度
    int[] up = new int[length];
    int[] down = new int[length];

    //填充值
    Arrays.fill(up, 1);
    Arrays.fill(down, 1);

    //结果值，因为每个数字都可以看做为一个最小的湍流子数组，所以初始值为1
    int ans = 1;

    for (int i = 1; i < length; i++) {
        //上升
        if (arr[i] > arr[i - 1]) {
            //更新上升数组并比较子数组最长长度
            up[i] = down[i - 1] + 1;
            ans = Math.max(ans, up[i]);
            //下降
        } else if (arr[i] < arr[i - 1]) {
            //更新下降数组并比较子数组最长长度
            down[i] = up[i - 1] + 1;
            ans = Math.max(ans, down[i]);
        }
    }

    return ans;
    
}
  • 时间复杂度：O(N)，只需要遍历一次数组。
  • 空间复杂度：O(N)，使用到两个额外数组。