leetcode 376摆动序列

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

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

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n=len(nums)
        if n<2:
            return n
        pre_length=1
        pre_flag=0
        for i in range(1,n):
            current_gap=nums[i]-nums[i-1]
            if current_gap==0:
                continue
            current_flag=1 if current_gap>0 else -1
            if pre_flag==0:
                pre_length+=1
                pre_flag=current_flag
            else:
                if current_flag!=pre_flag:
                    pre_length+=1
                    pre_flag=-1*pre_flag
        return pre_length

上面相同思路的一种简单方法：

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n=len(nums)
        if n<2:
            return n
        pre_minus=nums[1]-nums[0]
        if pre_minus!=0:
            count=2
        else:
            count=1
        for i in range(2,n):
            cur_minus=nums[i]-nums[i-1]
            if (cur_minus>0 and pre_minus<=0 ) or (cur_minus<0 and pre_minus>=0):  #可能会有之前差为0，但是这次开始算的情况
                count+=1
                pre_minus=cur_minus
        return count

这道题也可以用动态规划的思路解决
dp[i][0]表示以i为结尾，当前为降序的最长摆动序列长度
dp[i][1]表示以i为结尾，当前为升序的最长摆动序列长度

图片来自leetcode 题区

up结尾的摆动序列是由最长的以down结尾的序列转化过来
down结尾的摆动序列是由最长的以up结尾的序列转化过来
这种方式甚至可以很方便的求得序列，只需要每次加上添加位置即可

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n=len(nums)
        if n<2:
            return n
        up=1
        down=1
        for i in range(1,n):
            if nums[i]>nums[i-1]:
                up=down+1
            elif nums[i]<nums[i-1]:
                down=up+1
            else:
                continue
        return max(up,down)

就如下面这样

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n=len(nums)
        if n<2:
            return n
        up=[nums[0]]
        down=[nums[0]]
        for i in range(1,n):
            if nums[i]>nums[i-1]:
                up=down+[nums[i]]
            elif nums[i]<nums[i-1]:
                down=up+[nums[i]]
            else:
                continue
        return max(len(up),len(down))