题目

https://leetcode.cn/problems/longest-turbulent-subarray/

Given an integer arrayarr, return the length of a maximum size turbulent subarray of arr.

A subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

More formally, a subarray [arr[i], arr[i + 1], ..., arr[j]] of arr is said to be turbulent if and only if:

• For i <= k < j:
  arr[k] > arr[k + 1] when k is odd, and
  arr[k] < arr[k + 1] when k is even.

• Or, for i <= k < j:
  arr[k] > arr[k + 1] when k is even, and
  arr[k] < arr[k + 1] when k is odd.

Constraints：

• 1 <= arr.length <= 40000
• 0 <= arr[i] <= 10^9

单词批注

subarray 子数组

odd 奇数 even偶数

adjacent 相邻的

Constraints 约束

MY

• 写题过程

  一开始就是觉得先从基础的二维看一下能不能推（受到01背包的影响hh），发现还是二维根据题意f[i][j]则i表示以a[i]为最后一个数组的符合第1或第2的条件的最长子数组，那么把j的值定义为1或2；BUT，我不会写代码。

  于是我决定用同一种判断方法重复两次，确实过了，垃圾写法哈哈哈哈。

  我的代码有参考到昨天写的题的影响，直接采用了用当前位去推下一位，还是有学到的。

• 自己要注意的地方

  • 不要思维固化，觉得不是模板的样子就轻易否定自己
  • 我发现dp和回溯很明显不同的地方在于，回溯没有那么依赖于前一种状态，需要从前一种状态去推
  • dp代码：一定要注意遍历顺序 是否会保留上一层，我们是否需要保留上一层，这个可以帮助我们消除维度

From三叶姐姐

1. DP 如何分析，通过我们会先考虑一维 DP 能否求解，不行再考虑二维 DP。
2. 通常我们做 DP 题，都是先猜一个定义，然后看看这个定义是否能分析出状态转移方程帮助我们「不重不漏」的枚举所有的方案。一般我是直接根据答案来猜定义，这里是求最长子数组长度，所以我猜一个 f(i,j) 代表最长湍流子数组长度

参考代码

• 二维

class Solution {
    int maxTurbulenceSize(vector<int>& arr) {
        int len = arr.size();
        int ans = 1;
        int f[2][2];
        f[0][0] = f[0][1] = 1;
        for(int i = 1;i<len;i++){
            f[i][0] = f[i][1] = 1;
            if (arr[i] > arr[i - 1]) f[i][0] = f[i - 1][1] + 1;
            else if (arr[i] < arr[i - 1]) f[i][1] = f[i - 1][0] + 1;
            ans = max(ans, max(f[i % 2][0], f[i % 2][1]));
        }
        return ans;
    }
}

• 奇偶滚动

当 f[i][j] 状态的更新只依赖于 f[i−1][j] 的状态时！

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int len = arr.size();
        int ans = 1;
        //奇偶滚动 f[i][j] 状态的更新只依赖于 f[i−1][j] 的状态
        int f[2][2];
        f[0][0] = f[0][1] = 1;
        for(int i = 1;i<len;i++){
             f[i % 2][0] = f[i % 2][1] = 1;
            if (arr[i] > arr[i - 1]) f[i % 2][0] = f[(i - 1) % 2][1] + 1;
            else if (arr[i] < arr[i - 1]) f[i % 2][1] = f[(i - 1) % 2][0] + 1;
            ans = max(ans, max(f[i % 2][0], f[i % 2][1]));
        }
        return ans;
    }
};

• 维度消除

注意前一种状态的保存！

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int ans = 1;
        int f[2];
        f[0] =f[1]= 1;
        for(int i = 1;i<arr.size();i++){
        	int a = f[0],b = f[1];
            f[0] = arr[i - 1] < arr[i] ? b + 1 : 1;
            f[1] = arr[i - 1] > arr[i] ? a + 1 : 1;
            ans = max(ans, max(f[0], f[1]));
        }
        return ans;
        }
};