当 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 的最大湍流子数组的长度。
Example:
示例 1:
输入:[9,4,2,10,7,8,8,1,9]
输出:5
解释:(A[1] > A[2] < A[3] > A[4] < A[5])
示例 2:
输入:[4,8,12,16]
输出:2
示例 3:
输入:[100]
输出:1
提示:
1 <= A.length <= 40000
0 <= A[i] <= 10^9
Solutions
Solution ( 15ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public int maxTurbulenceSize ( int [] A ) {
int length = A . length ;
if ( length == 1 ) {
return 1 ;
} else if ( length == 2 ) {
return A [ 0 ] == A [ 1 ] ? 1 : 2 ;
}
int lastCOmpare = Integer . compare ( A [ 0 ], A [ 1 ]);
int presentCompare ;
int maxLength = 0 ;
int curLength = lastCOmpare == 0 ? 1 : 2 ;
for ( int i = 1 , len = length - 1 ; i < len ; i ++) {
presentCompare = Integer . compare ( A [ i ], A [ i + 1 ]);
if ( lastCOmpare == 0 ) {
lastCOmpare = presentCompare ;
curLength = lastCOmpare == 0 ? 1 : 2 ;
continue ;
} else if ( presentCompare == 0 ) {
lastCOmpare = presentCompare ;
if ( curLength > maxLength ) {
maxLength = curLength ;
}
curLength = 1 ;
} else if ( Math . abs ( presentCompare + lastCOmpare ) == 2 ) {
lastCOmpare = presentCompare ;
if ( curLength > maxLength ) {
maxLength = curLength ;
}
curLength = 2 ;
} else {
lastCOmpare = presentCompare ;
curLength ++;
}
}
if ( curLength > maxLength ) {
maxLength = curLength ;
}
return maxLength ;
}
}
Solution ( 22ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int maxTurbulenceSize ( int [] A ) {
int N = A . length ;
int ans = 1 ;
int anchor = 0 ;
for ( int i = 1 ; i < N ; ++ i ) {
int c = Integer . compare ( A [ i - 1 ], A [ i ]);
if ( i == N - 1 || c * Integer . compare ( A [ i ], A [ i + 1 ]) != - 1 ) {
if ( c != 0 ) ans = Math . max ( ans , i - anchor + 1 );
anchor = i ;
}
}
return ans ;
}
}
Solution (11ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int maxTurbulenceSize ( int [] A ) {
if ( A . length == 1 )
return 1 ;
int [] o = new int [ A . length - 1 ];
for ( int i = 0 ; i < A . length - 1 ; ++ i ) {
if ( A [ i + 1 ] - A [ i ] > 0 ) {
o [ i ]= 1 ;
} else if ( A [ i + 1 ] - A [ i ] < 0 ) {
o [ i ]=- 1 ;
} else {
o [ i ]= 0 ;
}
}
int count = 0 ;
int maxCount = 0 ;
for ( int i = 0 ; i < o . length - 1 ;++ i )
{
if ( o [ i ]* o [ i + 1 ]==- 1 )
{
count ++;
if ( maxCount < count )
maxCount = count ;
} else {
count = 0 ;
}
}
return maxCount + 2 ;
}
}
Notes
思路
显然,我们只需要关注相邻两个数字之间的符号就可以了。 如果用 -1, 0, 1
代表比较符的话(分别对应 <、 =、 >
),那么我们的目标就是在符号序列中找到一个最长的元素交替子序列 1, -1, 1, -1, ...
(从 1
或者 -1
开始都可以)。
这些交替的比较符会形成若干个连续的块 。我们知道何时一个块会结束:当已经到符号序列末尾的时候或者当序列元素不再交替的时候。
举一个例子,假设给定数组为 A = [9,4,2,10,7,8,8,1,9]
。那么符号序列就是 [1,1,-1,1,-1,0,-1,1]
。它可以被划分成的块为 [1], [1,-1,1,-1], [0], [-1,1]
。
算法
从左往右扫描这个数组,如果我们扫描到了一个块的末尾(不再交替或者符号序列已经结束),那么就记录下这个块的答案并将其作为一个候选答案,然后设置下一个元素(如果有的话)为下一个块的开头。