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 啦。

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

最后更新于