Leetcode 376.摆动序列

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
解释: 整个序列均为摆动序列。
示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

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

方法

方法1：动态规划 $O(n^2)$

$dp[i]=max(dp[i],dp[j]+1) if diff[i] \times diff[j]<0$

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        dp[i]表示nums[0,..,i+1]之前摆动序列最长长度
        """
        n=len(nums)
        if n<2:
            return n
        if len(set(nums))==1:
            return 1

        diff=[nums[i]-nums[i-1] for i in range(1,n)]
        dp=[1]*(n-1)                            # dp长度是n-1,nums长度是n

        for i in range(n-1):
            for j in range(i):
                if diff[i]*diff[j]<0:
                    dp[i]=max(dp[i],dp[j]+1)

        return max(dp)+1

方法2：贪心算法 $O(n)$

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        if n<2:
            return n

        stack=[]
        for n in nums:
            if not stack:
                stack.append(n)
            elif len(stack)==1:
                if n!=stack[-1]:          # stack只有一个元素，则只要n与其不重复，就入栈
                    stack.append(n)
            else:
                pre=stack[-1]-stack[-2]
                next=n-stack[-1]
                if pre*next<0:             # 一正一负，能形成摆动，入栈
                    stack.append(n)
                elif pre*next>0:           # 连续递增或连续递减，则将n替换栈顶元素          
                    stack[-1]=n            # 因为末尾变大后更容易找到下一个更小值
        return len(stack)

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        if n<2:
            return n

        ans=1
        cur=nums[0]
        increase_flag=None

        for i in range(1,n):
            if cur<nums[i]:
                if increase_flag!=True:
                    increase_flag=True
                    ans+=1
                cur=nums[i]
            elif cur>nums[i]:
                if increase_flag!=False:
                    increase_flag=False
                    ans+=1
                cur=nums[i]
            else:
                continue
        return ans

执行用时: 24 ms, 在Wiggle Subsequence的Python提交中击败了100.00% 的用户
内存消耗: 7 MB, 在Wiggle Subsequence的Python提交中击败了100.00% 的用户

• Leetcode Discussion
• Leetcode 讨论