每日一练：最长湍流子数组

978. 最长湍流子数组 - 力扣（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 * 104
• 0 <= arr[i] <= 109

解法-1 动态规划 O(N)：

        这个题与每日一练：等差数列划分-CSDN博客类似，nums[i] 能否与前面的数组构成湍流数组取决于nums[i]与nums[i]的大小关系，具体是大于还是小于又取决于nums[i-1]与nums[i-2]的大小关系，所以dp表需要初始化前两个位置。

        创建一个dp表f，存放以 i 为结尾的最长湍流数组的长度，填表的具体情况在代码中体现：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1)
            return n;

        vector<int> f(n);
        // 初始化
        f[0] = 1;
        if (arr[0] == arr[1])
            f[1] = 1;
        else
            f[1] = 2;

        int ret = f[1];
        for (int i = 2; i < n; i++) {
            if (arr[i] > arr[i - 1] && arr[i - 1] < arr[i - 2] ||
                arr[i] < arr[i - 1] && arr[i - 1] > arr[i - 2]) {
                f[i] = f[i - 1] + 1; // arr[i]与前面构成湍流数组
            } else if (arr[i] == arr[i - 1]) { // 不构成湍流数组且与arr[i-1]也不构成湍流数组
                f[i] = 1;
            } else { // 不构成湍流数组，但是与arr[i-1]构成长度为2的湍流数组
                f[i] = 2;
            }
            ret = max(ret, f[i]);
        }

        return ret;
    }
};

        优化-滑动数组减少内存消耗：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1)
            return n;

        int a,b,c;
        a = 1;
        if(arr[0]==arr[1])
            b = 1;
        else
            b = 2;

        int ret = b;
        for (int i = 2; i < n; i++) {
            if (arr[i] > arr[i - 1] && arr[i - 1] < arr[i - 2] ||
                arr[i] < arr[i - 1] && arr[i - 1] > arr[i - 2]) {
                c = b + 1; // arr[i]与前面构成湍流数组
            } else if (arr[i] == arr[i - 1]) { // 不构成湍流数组,且与arr[i-1]也不构成湍流数组
                c = 1;
            } else { // 不构成湍流数组，但是与arr[i-1]构成长度为2的湍流数组
                c = 2;
            }
            a = b;b = c;
            ret = max(ret, b);
        }

        return ret;
    }
};