Python O(n) time


  • 0
    A

    Iterate over the array, and not increment the counter if we are not interested.

    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 0: return 0
            if len(nums) == 1: return 1
            if len(nums) == 2: return 1
            diff = nums[1]-nums[0]
            if diff > 0:
                return self.computeMaxLength(nums, True)
            else:
                return self.computeMaxLength(nums, False)
                
        def computeMaxLength(self, nums, positive):
            c = 1
            diff = 0
            for i in range(0, len(nums)-1):
                diff = nums[i+1]-nums[i]
                if (diff > 0) and positive:
                    c += 1
                    positive = not positive
                if (diff < 0) and not positive:
                    c += 1
                    positive = not positive
            return c
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.