[Python] Documented solution in O(n) time that is easy to understand


  • 0
    class Solution(object):
        def wiggleMaxLength(self, nums):
            if not nums:
                return 0
            # we use this alternator to determine if we are
            # falling into a valley or climbing up a peak
            # False = falling, True = climbing
            alternator = False
            # this list will track the longest wiggle subsequence
            wiggle_stack = []
            wiggle_stack.append(nums[0])
    
            for num in nums[1:]:
                # if we have only one value we need to decide whether 
                # we start off by falling or climbing
                if len(wiggle_stack) == 1:
                    # we're climbing
                    if num > wiggle_stack[-1]:
                        wiggle_stack.append(num)
                    # we're falling (notice that we purposefully ignore the == case)
                    elif num < wiggle_stack[-1]:
                        alternator = True
                        wiggle_stack.append(num)
                # falling
                elif not alternator:
                    # num is larger than current peak so we update 
                    # the height of the peak to take the larger height
                    if num > wiggle_stack[-1]:
                        wiggle_stack[-1] = num
                    # num is less than current peak which means we
                    # have successfully fallen. Now we have to climb
                    elif num < wiggle_stack[-1]:
                        alternator = True
                        wiggle_stack.append(num)
                # climbing
                else:
                    # num is lower than current valley so we update
                    # the height of the valley to take the lower valley
                    if num < wiggle_stack[-1]:
                        wiggle_stack[-1] = num
                    # num is greater than current peak which means we
                    # have successfully climbed. Now we have to fall
                    elif num > wiggle_stack[-1]:
                        alternator = False
                        wiggle_stack.append(num)
            return len(wiggle_stack)
    

    Here is the code without comments for the Python wizards out there!

    class Solution(object):
        def wiggleMaxLength(self, nums):
            if not nums:
                return 0
            alternator = False
            wiggle_stack = []
            wiggle_stack.append(nums[0])
            for num in nums[1:]:
                if len(wiggle_stack) == 1:
                    if num > wiggle_stack[-1]:
                        wiggle_stack.append(num)
                    elif num < wiggle_stack[-1]:
                        alternator = True
                        wiggle_stack.append(num)
                elif not alternator:
                    if num > wiggle_stack[-1]:
                        wiggle_stack[-1] = num
                    elif num < wiggle_stack[-1]:
                        alternator = True
                        wiggle_stack.append(num)
                else:
                    if num < wiggle_stack[-1]:
                        wiggle_stack[-1] = num
                    elif num > wiggle_stack[-1]:
                        alternator = False
                        wiggle_stack.append(num)
            return len(wiggle_stack)
    

Log in to reply
 

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