Description
A subarray 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.
当 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 的最大湍流子数组的长度。
题目链接：https://leetcode.com/problems/longest-turbulent-subarray/
Difficulty: medium
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 <= A.length <= 40000
- 0 <= A[i] <= 10^9
分析
- 用li记录以当前数字结尾的字串的湍流子数组的长度；
- 向后遍历，若当前数字与下一个数字的大小关系与上一组数字的大小关系一致（若上一组关系是“大于”则这一组的关系是“小于”，反之则是大于，注：“等于”是不满足的），则满足长度加一；
- 反之置2；
- 初始为1；
- 返回li的最大值。
参考代码
class Solution:
def maxTurbulenceSize(self, A):
def get(a,b,i):
if(i%2==0):
if(a<b):
return True
else:
return False
else:
if(a>b):
return True
else:
return False
li=[1]
index=[]
for i in range(len(A)-1):
judge=get(A[i],A[i+1],i)
if(A[i]==A[i+1]):
index.append("#")
li.append(1)
continue
if(len(index)==0 or index[-1]=="#"):
index.append(judge)
li.append(2)
else:
if(judge==index[-1]):
index.append(judge)
li.append(li[-1]+1)
else:
index.append(judge)
li.append(2)
return max(li)