Easy to understand python O(n) short solution


  • 0
    G

    Actually inspired by the description of the problem itself XDDD.
    ""For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative.""
    Greedy solution, use deque so we have O(1) popleft.

    class Solution(object):
        def wiggleMaxLength(self, nums):
            from collections import deque
            if len(nums) <= 1: return len(nums)
            diff = deque([nums[i] - nums[i-1] for i in xrange(1, len(nums))])
            total = 1
            current = diff.popleft()
            while diff:
                val = diff.popleft()
                if val * current < 0 :
                    total += 1
                    current = val
            return total +1
    

  • 0

    You could use a generator instead of deque:

    def wiggleMaxLength(self, nums):
        if len(nums) <= 1: return len(nums)
        diff = (nums[i] - nums[i-1] for i in xrange(1, len(nums)))
        total = 1
        current = next(diff)
        for val in diff:
            if val * current < 0 :
                total += 1
                current = val
        return total +1

  • 0

    Oh and you fail test case [0,0].


  • 0
    G

    @StefanPochmann Thanks for pointing this out and fixing the test case.
    The way I handle it is to check if
    if sum(nums) == nums[0]*len(nums): return 1
    Not sure if it is the general way to fix this. :)


  • 0

    @guangying094 said in Easy to understand python O(n) short solution:

    if sum(nums) == nums[0]*len(nums): return 1

    That rather makes things worse, as it would for example return 1 for input [1,2,0] instead of the correct 3.


  • 0
    G

    @StefanPochmann Oops that's right lol. Thanks.
    So I need to check if every elements are equal.
    if all(x == nums[0] for x in nums) : return 1


  • 0

    Still doesn't really address the problem. For example your output for [1,1,17,5,10,13,15,10,5,16,8] is 2.


Log in to reply
 

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