最长湍流子数组

难度: Medium

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 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]。

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

输入：arr = [4,8,12,16]
输出：2

示例 3：

输入：arr = [100]
输出：1

提示：

1 <= arr.length <= 4 * 10⁴
0 <= arr[i] <= 10⁹

Submission

运行时间: 66 ms

内存: 18.8 MB

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [1] * n
        tail = arr[0]
        sign = 0
        for i in range(1, n):
            if arr[i] != tail and sign == 0:
                
                sign = 1 if arr[i] > tail else -1
                tail = arr[i]
                dp[i] = dp[i - 1] + 1
            elif sign == 1 and arr[i] < tail :
                sign = -1
                tail = arr[i]
                dp[i] = dp[i - 1] + 1
            elif sign == -1 and arr[i] > tail:
                sign = 1
                tail = arr[i]
                dp[i] = dp[i - 1] + 1
            else:#sign 和 差值不匹配
                if sign == -1 and arr[i] < tail:
                    sign = -1
                    tail = arr[i]
                    dp[i] = 2
                elif sign == 1 and arr[i] > tail:
                    sign = 1
                    tail = arr[i]
                    dp[i] = 2
                elif arr[i] == tail:
                    #print(i, arr[i], tail)
                    sign = 0
                    tail = arr[i]
                    dp[i] = 1
        #print(dp)
        return max(dp)

Explain

该题解使用动态规划方法求解最长湍流子数组的长度。定义dp[i]表示以arr[i]结尾的最长湍流子数组的长度。使用tail变量记录上一个元素的值，sign变量记录当前湍流子数组的比较符号，即在湍流子数组中，当前比较应该是大于还是小于。初始时，dp数组全部初始化为1（每个元素自身至少是长度为1的湍流子数组），tail初始化为arr[0]，sign初始化为0（表示还未确定比较方向）。遍历数组时，根据当前元素与tail的比较结果以及当前的sign状态，更新dp数组。如果当前元素与tail相等，湍流结束，dp[i]重置为1；如果符合当前的湍流模式（sign状态），则dp[i]等于dp[i-1]+1并更新sign；如果不符合当前模式，根据具体情况重置sign和dp[i]的值。最后返回dp数组中的最大值，即为最长的湍流子数组长度。

时间复杂度: O(n)

空间复杂度: O(n)

# class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        n = len(arr)  # 数组长度
        dp = [1] * n  # 初始化dp数组，每个位置最小湍流长度为1
        tail = arr[0]  # 初始化tail为第一个元素
        sign = 0  # 比较符号初始化
        for i in range(1, n):  # 遍历数组
            if arr[i] != tail and sign == 0:  # 如果当前元素与tail不同且未确定比较方向
                sign = 1 if arr[i] > tail else -1  # 确定比较方向
                tail = arr[i]  # 更新tail
                dp[i] = dp[i - 1] + 1  # 更新dp[i]
            elif sign == 1 and arr[i] < tail:  # 如果当前比较方向为大于且当前元素小于tail
                sign = -1  # 改变比较方向
                tail = arr[i]  # 更新tail
                dp[i] = dp[i - 1] + 1  # 更新dp[i]
            elif sign == -1 and arr[i] > tail:  # 如果当前比较方向为小于且当前元素大于tail
                sign = 1  # 改变比较方向
                tail = arr[i]  # 更新tail
                dp[i] = dp[i - 1] + 1  # 更新dp[i]
            else:  # 如果当前元素与tail相等或其他不符合当前湍流模式的情况
                if arr[i] == tail:  # 相等情况
                    sign = 0  # 重置比较方向
                    tail = arr[i]  # 更新tail
                    dp[i] = 1  # 重置dp[i]
                else:  # 不符合当前湍流模式
                    sign = 1 if arr[i] > tail else -1  # 重新确定比较方向
                    tail = arr[i]  # 更新tail
                    dp[i] = 2  # 重置dp[i]开始新的湍流
        return max(dp)  # 返回dp中的最大值，即最长湍流子数组的长度

Explore

在湍流子数组中，要求每个元素与前一个元素不相等，并且与前一个元素的大小关系要连续交替。当当前元素与tail（即前一个元素）相等时，这种大小关系被打破，因此无法形成湍流子数组。将dp[i]重置为1是因为任何单个元素可以被视为长度为1的湍流子数组。这种处理有助于在数组中明确标识湍流子数组的起始点，即每次遇到相等的元素，湍流子数组就在此处结束，新的可能的湍流子数组从下一个不同的元素开始。

如果当前元素不符合预期的湍流模式（即大于或小于之间的交替关系被破坏），但同时与前一个元素不相等，意味着这个元素可以与前一个元素组成一个新的长度为2的湍流子数组。此时，虽然不能延续之前的湍流子数组，但可以开始一个新的湍流子数组，因此dp[i]被设置为2。这反映了题解中尝试从每个可能的点重新开始计算湍流子数组的长度的策略。

在题解中，sign变量用于表示当前湍流子数组中元素的比较方向。其中，0表示比较方向尚未确定，通常是在子数组开始的位置或者当前元素与前一个元素相等时使用。1表示当前元素应该大于前一个元素，即预期下一个元素应该小于当前元素，形成一个'大于'的比较。-1表示当前元素应该小于前一个元素，即预期下一个元素应该大于当前元素，形成一个'小于'的比较。这种方法有助于追踪和维持湍流子数组的交替大小关系。

题解中从索引1开始遍历数组是因为需要将数组中的每个元素与其前一个元素进行比较。如果从索引0开始，则没有前一个元素可以用于比较，无法决定该元素与前一个元素的大小关系，因此无法判断是否符合湍流条件。从索引1开始，可以确保每次迭代都能访问到当前元素的前一个元素，从而正确地应用湍流子数组的定义和逻辑。