题目描述
当 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 的最大湍流子数组的长度。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-turbulent-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
样例
输入:[9,4,2,10,7,8,8,1,9]
输出:5
解释:(A[1] > A[2] < A[3] > A[4] < A[5])
又是求连续最长子数组类型的题,一般两种思路:
- 双指针:维护一个区间[l, r], r递增扩大区间,当不满足区间定义时,l递增缩短区间直到满足定义
- dp: 维护状态数组dp, dp[i]根据dp[i-1]的信息和当前值a[i]转移状态
算法1
(双指针) $O(n)$
维护[l,r]区间,该区间表示一个湍流子数组。同时维护一个字符变量pre,表示前一对值的大小关系(’=’, ‘>’, ‘<’),每次递增r去试图扩展区间,比较arr[r]和arr[r-1]的大小关系,再与pre比较
需要思考一下初始化的问题,可以假设初始状态为l == r == 0, 那么pre = ‘=’,此时再初始化l = 0, r = 1,表示要用r去试图扩展边界了,如果不满足定义再更新l。最后更新答案。
C++ 代码
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
char pre = '=';
int n = arr.size();
int res = 1;
for(int l = 0, r = 1; r < n; r ++){
char cur = arr[r-1] == arr[r] ? '=' : (arr[r-1] > arr[r] ? '>' : '<');
if(cur == '=') l = r;
else if(cur == pre) l = r - 1;
res = max(res, r - l + 1);
pre = cur;
}
return res;
}
};
算法2
(dp) $O(n)$
这里有两类状态,一类是arr[i] > arr[i-1], 另一类是a[i] < arr[i-1]. 因此我们可以定义两个状态数组:
down[i]: 以i结尾,arr[i][HTML_REMOVED]arr[i-1]的最长湍流子数组长度
因此状态转移方程为:
down[i] = up[i-1] + 1
up[i] = down[i-1] + 1
因为每个数自身都是一个长度为1的湍流子数组,所以up和down所有值初始化为1
C++ 代码
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
// down[i]: 以i结尾,arr[i]<arr[i-1]的最长湍流子数组长度
// up[i]: 以i结尾,arr[i]>arr[i-1]的最长湍流子数组长度
int n = arr.size();
vector<int> down(n, 1);
vector<int> up(n, 1);
int res = 1;
for(int i = 1; i < n; i ++){
if(arr[i] > arr[i - 1]){
up[i] = down[i-1] + 1;
}
else if(arr[i] < arr[i-1]){
down[i] = up[i-1] + 1;
}
res = max(res, max(up[i], down[i]));
}
return res;
}
};