Short 1-pass O(n) greedy solution in Python


  • 0
    class Solution:
        def wiggleMaxLength(self, nums):
            if not nums: return 0
            seq, idx, n, nex = [nums[0]], 1, len(nums), -1
            ops1 = (operator.le, operator.ge)
            while idx < n:
                while idx < n and nums[idx] == seq[-1]: 
                    idx += 1
                if idx >= n: break
                op, nex, idx  = ops1[nums[idx] > seq[-1]], nums[idx], idx + 1
                while idx < n and op(nums[idx], nex):
                    nex, idx = nums[idx], idx + 1
                seq.append(nex)
            return len(seq)
    

    Explanation (some parts borrowed from @StefanPochmann and his post):

    Imagine the given array contains [..., 10, 7, 11, 13, 17, 19, 23, 20, ...]. So increasing from 7 to 23. What can we do with that? Well we can't use more than two of those increasing numbers, as that wouldn't be wiggly. And if we do use two, we'd better use the 7 and the 23, as that offers the best extensibility (for example, the 19 wouldn't allow to next pick the 20 for the wiggly subsequence).

    And if we do use only one, it still should be either the 7 or the 23, as the 7 is the best wiggle-low and the 23 is the best wiggle-high of them. So whether we actually use the 7 and the 23 or not, we should not use 11, 13, 17, and 19.

    So we start from the first element (can you figure out why picking the first one as start is the best choice?) and depending on whether the next one is greater or lesser (skip dups, of course, done in second loop), we greedily pick the next num that maximizes the increasing streak or minimizes the decreasing streak (cause it's the best). This is done in the third loop. That will be the longest possible wiggle subsequence. I used operator.ge and operator.le for code conciseness.


Log in to reply
 

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