0978. 最长湍流子数组

题目地址 (978. 最长湍流子数组）

https://leetcode-cn.com/problems/longest-turbulent-subarray/

题目描述

当 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 的最大湍流子数组的长度。

 

示例 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

前置知识

• 滑动窗口

公司

• 暂无

思路

我们先尝试从题目给的例子打开思路。

对于 A 为 [9,4,2,10,7,8,8,1,9] 来说，我用这样的一个数组 arr 来表示 [-, -, +, -, +, 0, -, +]。其含义是 arr[i] 表示 A[i] - A[i - 1]的符号，其中：+ 表示正号，- 表示 负号，0 表示 A[i] 和 A[i - 1]相同的情况，那么显然 arr 的长度始终为 A 的长度 - 1。

那么不难得出，题目给出的剩下两个例子的 arr 为：[+, +, +] 和 []。

通过观察不难发现， 实际题目要求的就是正负相间的最大长度。如上的三个例子分别为：

我用粗体表示答案部分

• [-, -, +, -, +, 0, -, +]，答案是 4 + 1

• [+, +, +]，答案是 1 + 1

• []，答案是 0 + 1

于是使用滑动窗口求解就不难想到了，实际上题目求的是连续 xxxx，你应该有滑动窗口的想法才对，对不对另说，想到是最起码的。

由于 0 是始终不可以出现在答案中的，因此这算是一个临界条件，大家需要注意特殊判断一下，具体参考代码部分。

代码

代码中使用了一个小技巧，就是 a ^ b >= 0 说明其符号相同，这样比相乘判断符号的好处是可以避免大数溢出。

class Solution:
    def maxTurbulenceSize(self, A: List[int]) -> int:
        ans = 1
        i = 0
        for j in range(2, len(A)):
            if (A[j] == A[j - 1]):
                i = j
            elif (A[j] - A[j - 1]) ^ (A[j - 1] - A[j - 2]) >= 0:
                i = j - 1
            ans = max(ans, j - i + 1)
        return ans

复杂度分析

• 时间复杂度：$O(N)$

• 空间复杂度：$O(1)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。