题目地址：https://leetcode.com/problems/longest-turbulent-subarray/
题目描述
Asubarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:
- For i
<= k< j, A[k] >A[k+1] when k is odd, and A[k]< A[k+1] when k is even; - OR, for i
<= k< j, A[k] >A[k+1] when k is even, and A[k]< A[k+1] when k is odd. That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
Return the length of a maximum size turbulent subarray of A.
Example 1:
Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])
Example 2:
Input: [4,8,12,16]
Output: 2
Example 3:
Input: [100]
Output: 1
Note:
1、 1<=A.length<=40000；
2、 0<=A[i]<=10^9；
题目大意
如果相邻的两个数字的差在大于0和小于0这两种情况中互相翻转，那么说明这个子数组是符合要求的。求最长的符合要求的子数组。
解题方法
虫取法
虫取法就是前后指针交替前进的方式。
对于这个题来说，我们先固定左侧的指针left，然后把右侧指针right向右移动，我使用了isde来表示上一次的相邻数字的差的符号，每次把当前的相邻数字符号和上一次的进行判断。需要注意的是题目要求必须翻转，如果连续数字是相等的则不符合要求。
移动的时候需要注意是不是相邻数字的差交替的：
如果是交替的，那么更新现在的相邻数字差的符号并且更新最长子串的长度；
如果不是交替的，那么需要更新left指针，这里的不是交替有两个情况，一是相等，二是连续的递增或者相减。如果right指向的元素是连续两个相等的，那么left指向right当前的位置当做新的起点；如果是A[right - 2]，A[right - 1]，A[right]三者有序的情况，那么把left更新到right-1的位置，此时right不要向右移动，相当于把left = right - 1当做新的数组起始位置。
举个栗子：
[9,4,2,10,7,8,8,1,9]
9,4,2是单调递减的三个数字，此时应该把left移动到4的位置，right仍然指向2，开始新的遍历过程。
当来回翻转，right到了第二个8的时候，此时子数组是4,2,10,7,8,8，已经不满足翻转条件，此时把left指向right为第二个8的位置，然后开始新的遍历过程。
再举个栗子：
[1,1,1,1,1,1,1]
这样都是连续相等的数值，那么A[right] == A[right - 1]会一直成立，所以每次都把left更新到right的位置，则没有一个构成翻转的条件，res不更新。由此也可见，应该把满足要求的最小的子数组的长度res初始化为1.
c++代码如下：
class Solution {
public:
int maxTurbulenceSize(vector<int>& A) {
const int N = A.size();
if (N == 1) return 1;
int res = 1;
int left = 0, right = 1;
bool isde = false;
while (right < N) {
if (A[right] == A[right - 1]) {
left = right;
right++;
} else if (right - left == 1 || (A[right] - A[right - 1] < 0 != isde)) {
isde = A[right] - A[right - 1] < 0;
res = max(res, right - left + 1);
right ++;
} else {
left = right - 1;
}
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发