Hexo

2020-12-14

思路

贪心，基于取极大值和极小值会比不取这些值得到的摆动数组要长(至少也相等)的推论(画图就很直观)，对于上升(可以等于)的连续子序列，其实我们可以只取首尾；同样的下降也进行同样的操作，这样每一步都取最长摆动序列：

如[1,17,5,10,13,15,10,5,16,8]进行上述的操作：

[1, 17]取首尾得到还是[1, 17]
[17, 5]取首尾还是[17, 5]
[5, 10, 13, 15]取首尾是[5, 15]
[15, 10, 5]取首尾是[15, 5]
接下来依次是[5, 16]和[16, 8]
所以得到的序列会是[1, 17, 5, 15, 5, 16, 8]
观察其中的第3步，其实这里面的5是确定的前面取的，后面的10, 13, 15对于这一段来说取哪个都是上升的，但是为了后面更有可能下降，那么贪心取最大值15是最好的。

代码

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # c用来记录前一个差值是下降/上升的，默认0
        n, c, res = len(nums), 0, 1 
        if n < 2:
            return n
        for i in range(1, n):
            x = nums[i] - nums[i - 1]
            # 如果有差值才继续处理
            if x:
                # <0代表有上升下降的交替，=0是初始情况的判断
                if x * c <= 0:
                    res += 1
                c = x
        return res