当 A 的子数组 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]。
也就是说,如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
示例 1:
1 | 输入:[9,4,2,10,7,8,8,1,9] |
示例 2:
1 | 输入:[4,8,12,16] |
示例 3:
1 | 输入:[100] |
思维~
官方题解有滑窗,有 DP,但是我另辟蹊径,用一种纯思维的方式,首先求两两数的差值,存入 diff 数组:
- arr[i]>arr[i+1],存入 $1$
- arr[i]<arr[i+1],存入 $-1$
- arr[i]=arr[i+1],存入 $0$
求得这个差值数组之后,我们就所有找的最大长度,无非就是求 $1,-1,\cdots,-1,1$ 序列的最大长度,设一个 $mx$ 变量维护最大值即可,对某一位置 $i$ 判断下面两种情况:
- diff[i]=0,此时必须把 mx 置 0,因为差值为 0 时最大长度为 1
- diff[i]≠0,若 diff[i]+diff[i+1]=0,mx++;若 diff[i]+diff[i+1]≠0,把 mx 置 1,因为差值不为 0 时的最大长度为 2
每次循环 ans=max(ans,mx+1),因为 mx 个差值对应 mx+1 个数,AC代码如下:
1 | class Solution { |