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。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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