leetcode每日一题：376.摆动序列

leetcode每日一题：376.摆动序列：eetcode-cn.com/problems/wiggle-subsequence/

一起刷题吧

一、题意分析

输入：整数数组
输出：最长的摆动子序列长度，子序列即要求保证数值的相对位置，摆动序列的定义：差值呈现正负交替的情况
难度：中等
标签：贪心、动态规划
注意：

• 长度小于 2 的时候，也是摆动序列
• 最好能用 O(N) 的时间复杂度解决

示例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

二、参考代码

• 首先我们来看下贪心的思路：

这个题目其实最容易理解的解法是通过画折线图，通过折线图，我们可以很容易发现，当我们尽可能多的保留摆动子序列，并且保证这些摆动子序列连接后仍然是摆动序列，就能得到最长的摆动序列。

参考下面这个题解，看图就能明白这个思路：

https://leetcode-cn.com/problems/wiggle-subsequence/solution/376-bai-dong-xu-lie-tan-xin-jing-dian-ti-vyxt/

这里先给出我的实现代码：

from typing import List


class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums_len = len(nums)
        if nums_len < 2:
            return nums_len

        pre = nums[0]
        pos = 1
        # 找到第一个和 nums[0] 不相等的位置
        while pos < nums_len and nums[pos] == pre:
            pos += 1
        # 如果全部相等，则返回 1
        if pos == nums_len:
            return 1
        # ans 记录摆动序列的长度，初始时有 pre 和 nums[pos] 组成的序列，因此初始值为 2
        ans = 2
        # 记录前一次差值是正还是负，正为 true，负为 false
        positive = (nums[pos] - pre) > 0
        # 修改 pre 的值
        pre = nums[pos]
        # 循环遍历 pos 之后的数值
        for i in range(pos + 1, nums_len):
            # 如果值相等，即差值为 0，则继续
            if nums[i] == pre:
                continue
            # 如果差值符号相同，则继续
            if ((nums[i] - pre) > 0) == positive:
                # 需要注意此处，当符号相同时需要更新 pre
                # 比如 [33,53,12,64,50,41,50,41,50,41,50,41,50,41,50,41,50,41] 这个情况
                # 通过拆线图，很容易看出来，当差值符号相同时，即此时拆线呈一个单调递增或递减的情况，这个时候我们应该记录单调的最值，这样才能保证摆动序列最长
                pre = nums[i]
                continue
            # 差值不相等，则做记录，并修改 pre、positive 的值
            ans += 1
            pre = nums[i]
            positive = not positive
        return ans


s = Solution()
print(s.wiggleMaxLength([1, 7, 4, 9, 2, 5]))
print(s.wiggleMaxLength([1, 17, 5, 10, 13, 15, 10, 5, 16, 8]))
print(s.wiggleMaxLength([1, 2, 3, 4, 5, 6, 7, 8, 9]))
print(s.wiggleMaxLength([0, 0]))
print(s.wiggleMaxLength([33, 53, 12, 64, 50, 41, 45, 21, 97, 35, 47, 92, 39, 0, 93, 55, 40, 46, 69, 42, 6, 95, 51, 68, 72, 9, 32, 84, 34, 64, 6, 2, 26, 98, 3, 43, 30, 60, 3, 68, 82, 9, 97, 19, 27, 98, 99, 4, 30, 96, 37, 9, 78, 43, 64, 4, 65, 30, 84, 90, 87, 64, 18, 50, 60, 1, 40, 32, 48, 50, 76, 100, 57, 29, 63, 53, 46, 57, 93, 98, 42, 80, 82, 9, 41, 55, 69, 84, 82, 79, 30, 79, 18, 97, 67, 23, 52, 38, 74, 15]))

执行效果：

执行用时：
44 ms
, 在所有 Python3 提交中击败了
67.09%
的用户
内存消耗：
14.9 MB
, 在所有 Python3 提交中击败了
5.16%
的用户

特别需要注意当符号相同时的处理情况，这一点通过代码中给出的特殊示例，通过画折线图也很容易明白。

对上述代码优化，参考了官方贪心解法的代码，其实题目最后的值就是所有先增后减序列的个数和。因为从上面我们的解法可以看出来，我们的序列其实是增、减序列的组合，当有连续增或减时，当再次出来反向序列，这个反向序列一定可以连接前面的摆动序列并组成新的摆动序列。

比如：某个序列，它从 [i, j] 这一段是一个摆动序列，从 j 开始直到 j+m 一直单调，假设是单调递减(其实这里也可以把相等的情况包入进去，即使相等，也不会影响最终的结论)，而 [j+m-1, j+m+n] 又是一个摆动序列。从前面的假设我们可以知道这个序列满足：

# 因为 [j, j+m] 单调递减，而 [i, j] 是摆动序列
# 即从 j+1 开始由于单调减，导致不能继续组合成摆动序列
# 因此摆动序列最后两个元素满足：
arr[j] < arr[j-1]

# 而从 [j, j+m] 一直单调递减，因此有：
arr[j+m] <= arr[j]

# 从 j+m-1 开始到 j+m+n 又出现摆动序列，因此一定有
arr[j+m] < arr[j+m-1]
arr[j+m] > arr[j+m+1]

# 因此两段摆动序列分别为：
arr[i], arr[i+1], ... , arr[j]，且最后两个元素的差值为负
arr[j+m-1], arr[j+m], ... , arr[j+m+n]，且开始两个元素的差值为负

# 两段序列做组合后要想仍然是一个摆动序列，其实直接用 arr[j+m-1] 将 arr[j] 替换就可以了
# 这是因为 arr[j+m-1] < arr[j]，因此 arr[j+m-1] < arr[j-1]
# 所以第一段摆动序列的差值交替情况不会改变
# 而第二段并没有产生变化
# 所以组合后应该为

arr[i], arr[i+1], ... , arr[j-1], arr[j+m-1], ... , arr[j+m+n]

# 证明完毕

实现代码如下：

# 参考官方题解修改：
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums_len = len(nums)
        if nums_len < 2:
            return nums_len

        prediff = nums[1] - nums[0]
        # ans 记录摆动序列的长度
        ans = 2 if prediff != 0 else 1
        # 循环遍历 pos 之后的数值
        for i in range(2, nums_len):
            diff = nums[i] - nums[i - 1]
            # 只要差值不相等，则加入统计
            if (diff > 0 and prediff <= 0) or (diff < 0 and prediff >= 0):
                ans += 1
                prediff = diff
        return ans

那么到底什么地方用到的贪心呢？其实当有差值不等时就加入序列，这样得到的最终序列就是最长的摆动序列。

• 接着我们来看下动态规划的实现思路：

首先我们要明白，对于一个摆动序列，它的结尾有两种可能：

1. 结尾两个元素差值为正
2. 结尾两个元素差值为负

我们通过 P(i) 表示前 i 个元素里结尾两个元素差值是正值的最长子序列个数，N(i) 表示前 i 个元素里结尾两个元素差值是负数的最长子序列个数。

我们先来分析 P(i)，如果 arr[i] > arr[i-1]，因为 P(i-1) 结尾已经是正数，所以没办法再有改变，但 N(i-1) 是可以增加1个的（这个通过前面的贪心思路证明里已经证明过了）；而如果 arr[i] <= arr[i-1]，无论是 P(i-1) 还是 N(i-1)，都没办法再增加。

同时对 N(i) 也是一样的分析。因此得出结论如下：

if arr[i] > arr[i-1]:
P(i) = max(P(i-1), N(i-1) + 1)
else:
P(i) = P(i-1)

if arr[i] < arr[i-1]:
N(i) = max(P(i-1)+1, N(i-1))
else:
N(i) = N(i-1)

# 最终结果：
return max(P(j), N(j)) 
j = len(arr) - 1

参考代码如下：

from typing import List


class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums_len = len(nums)
        if nums_len < 2:
            return nums_len

        P = [1] * len(nums)
        N = [1] * len(nums)

        for i in range(1, nums_len):
            diff = nums[i] - nums[i - 1]
            if diff > 0:
                P[i] = max(P[i - 1], N[i - 1] + 1)
                N[i] = N[i - 1]
            elif diff == 0:
                N[i] = N[i - 1]
                P[i] = P[i - 1]
            else:
                N[i] = max(P[i - 1] + 1, N[i - 1])
                P[i] = P[i - 1]
        return max(P[nums_len - 1], N[nums_len - 1])

对于动态规划，时间空间复杂度都为 O(N)，时间上基本已经最优，空间上还有优化的余地，我们其实并不需要存储整个数组，只需要前一次的状态即可，因此可将两个数组改成两个变量，这样空间复杂度能达到 O(1)，优化后代码实现参考如下：

from typing import List


class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums_len = len(nums)
        if nums_len < 2:
            return nums_len

        # 初始值都为1，即第一个元素
        lp = 1
        ln = 1

        for i in range(1, nums_len):
            diff = nums[i] - nums[i - 1]
            if diff > 0:
                lp = max(lp, ln + 1)
            elif diff < 0:
                ln = max(lp + 1, ln)
        return max(lp, ln)