0978. 最长湍流子数组
大约 2 分钟
0978. 最长湍流子数组
- 标签:数组、动态规划、滑动窗口
- 难度:中等
题目大意
给定一个数组 arr
。当 arr
的子数组 arr[i]
,arr[i + 1]
,...
, arr[j]
满足下列条件时,我们称其为湍流子数组:
- 若
i <= k < j
,当k
为奇数时,arr[k] > arr[k + 1]
,且当k
为偶数时,arr[k] < arr[k + 1]
; - 或若
i <= k < j
,当k
为偶数时,arr[k] > arr[k + 1]
,且当k
为奇数时,arr[k] < arr[k + 1]
。 - 也就是说,如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是湍流子数组。
要求:返回给定数组 arr
的最大湍流子数组的长度。
解题思路
湍流子数组实际上像波浪一样,比如 arr[i - 2] > arr[i - 1] < arr[i] > arr[i + 1] < arr[i + 2]
。所以我们可以使用双指针的做法。具体做法如下:
- 使用两个指针
left
、right
。left
指向湍流子数组的左端,right
指向湍流子数组的右端。 - 如果
arr[right - 1] == arr[right]
,则更新left = right
,重新开始计算最长湍流子数组大小。 - 如果
arr[right - 2] < arr[right - 1] < arr[right]
,此时为递增数组,则left
从right - 1
开始重新计算最长湍流子数组大小。 - 如果
arr[right - 2] > arr[right - 1] > arr[right]
,此时为递减数组,则left
从right - 1
开始重新计算最长湍流子数组大小。 - 其他情况(即
arr[right - 2] < arr[right - 1] > arr[right]
或arr[right - 2] > arr[right - 1] < arr[right]
)时,不用更新left
值。 - 更新最大湍流子数组的长度,并向右移动
right
。直到right >= len(arr)
时,返回答案ans
。
代码
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
left, right = 0, 1
ans = 1
while right < len(arr):
if arr[right - 1] == arr[right]:
left = right
elif right != 1 and arr[right - 2] < arr[right - 1] and arr[right - 1] < arr[right]:
left = right - 1
elif right != 1 and arr[right - 2] > arr[right - 1] and arr[right - 1] > arr[right]:
left = right - 1
ans = max(ans, right - left + 1)
right += 1
return ans