摆动序列-贪心376-python

没看答案，时间复杂度O(n)，空间复杂度O(1)，但实现过于复杂不推荐。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        res = n = len(nums)
        if n == 1:
            return res
        i, j = 0, 1
        if nums[1]-nums[0] > 0:
            pre = 1
        elif nums[1]-nums[0] < 0:
            pre = -1
        else:
            pre = 0

        for cur in range(2, n):
            tmp = nums[cur] - nums[cur-1]
            if tmp < 0:
                if pre != -1:
                    if pre == 1:
                        res -= j-i-1
                    if pre == 0:
                        res -= j-i
                    i = cur-1
                    pre = -1

            if tmp > 0:
                if pre != 1:
                    if pre == -1:
                        res -= j-i-1
                    if pre == 0:
                        res -= j-i
                    i = cur-1
                    pre = 1

            j = cur

        if pre == 0:
            res -= j-i
        else:
            res -= j-i-1
        
        return res

简化版，时间复杂度O(n)，空间复杂度O(1)。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return n
        '''
        对于一段递增或递减的序列，我们只需要保留两个端点，中间节点都不计入结果
        pre: 记录前一段的正负情况
        tmp：记录当前一段的正负情况
        当pre与tmp异号时更新res和pre
        '''


        pre = nums[1] - nums[0]
        res = 1 if pre == 0 else 2

        for i in range(2, n):
            tmp = nums[i] - nums[i-1]
            # pre等于0是为了包括pre初始化为0的情况，pre非0后不会再次等于0
            # 因为tmp为0时不会进入if，也就不会更新pre
            if (tmp < 0 and pre >= 0) or (tmp > 0 and pre <= 0):
                res  = 1
                pre = tmp
        
        return res

这篇好文章是转载于：学新通技术网