给定一个整数数组 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]
。
- 当
示例 1:
输入:arr = [9,4,2,10,7,8,8,1,9] 输出:5 解释:arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2:
输入:arr = [4,8,12,16] 输出:2
示例 3:
输入:arr = [100] 输出:1
提示:
1 <= arr.length <= 4 * 104
0 <= arr[i] <= 109
方法一:动态规划
我们定义
对于
由于
时间复杂度
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
ans = f = g = 1
for a, b in pairwise(arr):
ff = g + 1 if a < b else 1
gg = f + 1 if a > b else 1
f, g = ff, gg
ans = max(ans, f, g)
return ans
class Solution {
public int maxTurbulenceSize(int[] arr) {
int ans = 1, f = 1, g = 1;
for (int i = 1; i < arr.length; ++i) {
int ff = arr[i - 1] < arr[i] ? g + 1 : 1;
int gg = arr[i - 1] > arr[i] ? f + 1 : 1;
f = ff;
g = gg;
ans = Math.max(ans, Math.max(f, g));
}
return ans;
}
}
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int ans = 1, f = 1, g = 1;
for (int i = 1; i < arr.size(); ++i) {
int ff = arr[i - 1] < arr[i] ? g + 1 : 1;
int gg = arr[i - 1] > arr[i] ? f + 1 : 1;
f = ff;
g = gg;
ans = max({ans, f, g});
}
return ans;
}
};
func maxTurbulenceSize(arr []int) int {
ans, f, g := 1, 1, 1
for i, x := range arr[1:] {
ff, gg := 1, 1
if arr[i] < x {
ff = g + 1
}
if arr[i] > x {
gg = f + 1
}
f, g = ff, gg
ans = max(ans, max(f, g))
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
function maxTurbulenceSize(arr: number[]): number {
let f = 1;
let g = 1;
let ans = 1;
for (let i = 1; i < arr.length; ++i) {
const ff = arr[i - 1] < arr[i] ? g + 1 : 1;
const gg = arr[i - 1] > arr[i] ? f + 1 : 1;
f = ff;
g = gg;
ans = Math.max(ans, f, g);
}
return ans;
}