遵化市有做奇麟网站的吗网站优化推广公司

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;}
};