leetcode 376. 摆动序列 python

leetcode 376. 摆动序列 python

题目描述：

 

题解：

1.如果输入nums只有一个元素返回1，如果nums有两个元素，如果两个数字不等则返回2，否则返回1.

2.计算nums数组中相邻数字的差，保存在gaps数组。最终摇摆序列的长度=max(第一个差值为正数的序列最长长度，第一个差值为负数的序列最长长度)+1，分别用p_len n_len记录第一个差值为正数和负数的序列长度，p_start，n_start分别记录差值为正数和负数的开始位置。

3.分别从p_start依次寻找差值为负，正，负....记录长度，n_start做相同 *** 作。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return len(nums)
        if len(nums) == 2:
            if nums[0] != nums[1]:
                return 2
            else:
                return 1
        gaps = []
        n = len(nums)
        for i in range(n - 1):
            gaps.append(nums[i + 1] - nums[i])
        p_len = 0
        n_len = 0
        p_start = 0
        n_start = 0
        find_p = 0
        find_n = 0
        for i in range(n - 1):
            if gaps[i] > 0:
                p_start = i
                p_len = 1
                find_p = 1
                break
        for i in range(n - 1):
            if gaps[i] < 0:
                n_start = i
                n_len = 1
                find_n = 1
                break
        p_flag = -1
        for i in range(p_start + 1, n - 1):
            if gaps[i] * p_flag > 0:
                p_len = p_len + 1
                p_flag = -p_flag
        n_flag = 1
        for i in range(n_start + 1, n - 1):
            if gaps[i] * n_flag > 0:
                n_len = n_len + 1
                n_flag = -n_flag
        return max(p_len, n_len) + 1