题目

难度：★★★☆☆
类型：数组
方法：动态规划，贪心算法

传送门

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

例如， [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：动态规划

数组问题常常用空间代替时间的动态规划来做，针对此问题，动态规划的一般步骤：

数组定义。这里定义两个数组end_with_up和end_with_down，维度与输入数组是一致的，end_with_up[i]（0<=i<len(nums)）表示以nums[0:i]子数组中的最长的摆动数组的长度，且该摆动数组倒数第一个元素nums[i]大于倒数第二个元素。end_with_up[i]（0<=i<len(nums)）表示以nums[0:i]子数组中的最长的摆动数组的长度，且该摆动数组倒数第一个元素nums[i]小于倒数第二个元素。

数组初始化：两个数组中所有元素都初始化为1，因为摆动序列最小长度也是1。

状态转移方程。我们刚刚定义的两个数组是要在迭代过程中互相用到的。具体的用法是：

两次遍历，从1到len(nums)-1遍历数组，确定了子数组的寻找范围[1,i]，也就是从0到i的下标位置，这一层遍历，是为了填写end_with_up[i]和end_with_down[j]的，设置下标j（1<=i<len(nums)），确定了第二层遍历的元素nums[j]；第二层遍历就是在子数组中寻找可以使得end_with_up[i]和end_with_down[i]最大的组合方式，设置下标j（0<=j<i），确定了第二层遍历的元素nums[j]。

当nums[i]与nums[j]不相等的时候，就可以更新两个数组中的其中一个，具体方式是：
如果nums[j]<nums[i]，那么一定可以组成以这两个数结尾的摆动数组，由于最后两个数是上升的，所以需要更新的是end_with_up，考虑到当前该位置可能已经有值，取end_with_up[i] = max(end_with_up[i], end_with_down[j]+1)，这里的+1实际上的含义就是在摆动数组末尾增加了数字nums[i]；

同样的，如果nums[j]>nums[i]，那么一定可以组成以这两个数结尾的摆动数组，由于最后两个数是上升的，所以需要更新的是end_with_down，考虑到当前该位置可能已经有值，取end_with_down[i] = max(end_with_down[i], end_with_up[j]+1)，这里的+1实际上的含义就是在摆动数组末尾增加了数字nums[i]。

特殊情况：输入为空数组，直接返回零。

class Solution:
    def wiggleMaxLength(self, nums):
        if not nums:
            return 0

        end_with_up = [1 for _ in range(len(nums))]
        end_with_down = [1 for _ in range(len(nums))]

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    end_with_up[i] = max(end_with_up[i], end_with_down[j]+1)
                elif nums[j] > nums[i]:
                    end_with_down[i] = max(end_with_down[i], end_with_up[j]+1)
        return max(end_with_up+end_with_down)

方法2：贪心

道理其实与以上类似，只是把两个动态规划用的数组换成了两个变量p和q，而且遍历过程也做了简化，时间复杂度和空间复杂度都加倍简化。

class Solution:
    def wiggleMaxLength(self, nums):
        if not nums:
            return 0
        p = q = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                p = q + 1
            elif nums[i] < nums[i-1]:
                q = p + 1
        return max(p, q)

如有疑问或建议，欢迎评论区留言~