力扣题解（ 最长湍流子数组）

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]。

本题看似例子很长，实则很简单，即湍流数组形状为W型或者M型即可（认为中间比两边高，或者中间比两边低，然后每间隔一个都符合这个定律）（其实所谓w，m也不过就是开始位置差了一个而已）。因此做法也很简单，分情况讨论即可。注意本题如果前后两个元素相等，则必定构不成湍流数组。

对于偶数位置高的，若第i个仍满足这个定律，则长度加1，而这个满足则偶数位置低的那个一定不满足，因此那个的长度变为0.对奇数位置高的同理。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {

     int n=arr.size();

     vector<int>m(n,0);
     vector<int>w(n,0);
     m[0]=w[0]=1;
     for(int i=1;i<n;i++)
     {
        if(i%2==1)
        {
            //n为偶
            if(arr[i]>arr[i-1])
            {
                m[i]=m[i-1]+1;
                w[i]=1;
            }
            else if(arr[i]<arr[i-1])
            {
                w[i]=w[i-1]+1;
                m[i]=1;
            }
            else
            {
                m[i]=w[i]=1;
            }
        }else 
        {
              //n为奇
            if(arr[i]<arr[i-1])
            {
                m[i]=m[i-1]+1;
                w[i]=1;
            }
            else if(arr[i]>arr[i-1])
            {
                w[i]=w[i-1]+1;
                m[i]=1;
            }
            else
            {
                m[i]=w[i]=1;
            }
        }
     }

     int ret=1;
     for(int i=1;i<n;i++)
     {
        int nm=max(m[i],w[i]);
        ret=max(nm,ret);
     }
     
     return ret;
     
     
         }
};