摆动序列

难度: Medium

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

进阶：你能否用 O(n) 时间复杂度完成此题?

Submission

运行时间: 17 ms

内存: 16.1 MB

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        last = nums[0]
        res = 1
        flag = 0
        for i in range(1,len(nums)):
            if nums[i]!=last:
                if flag == 1:
                    if nums[i]-last<0:
                        res+=1
                        last = nums[i]
                        flag = -1
                    else:
                        last = nums[i]
                        continue
                elif flag == -1:
                    if nums[i]-last>0:
                        res+=1
                        last = nums[i]
                        flag = 1
                    else:
                        last = nums[i]
                        continue
                else:
                    if nums[i]-last > 0:
                        flag = 1
                    else:
                        flag = -1
                    res += 1
                    last = nums[i]
        return res

Explain

这个题解的思路是遍历数组，用一个变量 flag 来记录前一个差值的正负。如果当前差值和前一个差值符号相反，则摆动序列长度加1，并更新 last 为当前元素。如果当前差值和前一个差值符号相同，则只更新 last 为当前元素，不增加摆动序列长度。flag 初始为0，遇到第一个非0差值时，根据正负设置 flag 为1或-1。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        last = nums[0]  # 记录前一个元素的值
        res = 1  # 记录摆动序列当前长度
        flag = 0  # 记录前一个差值的正负，初始为0表示没有差值
        for i in range(1,len(nums)):
            if nums[i]!=last:  # 当前元素和前一个元素不相等
                if flag == 1:  # 前一个差值为正
                    if nums[i]-last<0:  # 当前差值为负
                        res+=1  # 摆动序列长度加1
                        last = nums[i]  # 更新 last 为当前元素
                        flag = -1  # 更新 flag 为 -1，表示当前差值为负
                    else:
                        last = nums[i]  # 更新 last 为当前元素
                        continue  # 当前差值仍为正，不增加摆动序列长度
                elif flag == -1:  # 前一个差值为负
                    if nums[i]-last>0:  # 当前差值为正
                        res+=1  # 摆动序列长度加1
                        last = nums[i]  # 更新 last 为当前元素
                        flag = 1  # 更新 flag 为 1，表示当前差值为正
                    else:
                        last = nums[i]  # 更新 last 为当前元素
                        continue  # 当前差值仍为负，不增加摆动序列长度
                else:  # 第一次遇到非0差值
                    if nums[i]-last > 0: 
                        flag = 1  # 差值为正，设置 flag 为 1
                    else:
                        flag = -1  # 差值为负，设置 flag 为 -1
                    res += 1  # 摆动序列长度加1
                    last = nums[i]  # 更新 last 为当前元素
        return res  # 返回最长摆动子序列的长度

Explore

在题解中，flag的初始值设为0，它会保持为0直到遇到第一个非0差值。如果数组中的所有元素相等或者数组只有一个元素，则整个遍历过程中，flag将始终为0。这种情况下，算法的逻辑是正确的，因为一个恒定的序列或单个元素的序列不具备摆动的特性，所以摆动序列的长度应该为1。因此，flag保持为0不会影响算法的正确性和完整性。

在题解的算法中，当遇到连续的相同数字时，由于差值为0，所以不会更新res（摆动序列的长度）。这些数字在计算摆动序列时被视为一个元素处理，即在检测到差值变化前，连续的相同数字仅算作序列中的一个点。因此，这些连续相同的数字不会增加摆动序列的长度。

在算法实现中，flag初始设为0，并在遍历过程中只在遇到第一个非0差值时修改flag的值（从0变为1或-1）。一旦flag的值被设定后，它只会在遇到符号相反的差值时才会变更。因此，通过检查flag是否为0，我们可以确保只在第一次遇到非0差值时对其进行处理，后续的非0差值将根据当前flag值和差值的关系来处理，而不会重新设定flag。

如果数组中所有元素都相同，那么所有的差值都为0，flag将保持其初始值0，last将不断更新为相同的值，但res（摆动序列的长度）始终维持为1。这是正确的，因为一个全相同元素的数组不具备摆动性，其摆动序列的最大长度应为1。因此，算法在这种情况下的输出是正确的。