A (maybe) different greedy O(n) approach, 7 lines, can be even shortened


  • 0
    X

    Assume you plot these numbers, then you'll see a mountain like shape (/\/\/\/\/\), which is going up and down. Now it's pretty clear that the optimal answer is just how many "turning points" that this "mountain" has.

    Now, if we know the mountain is firstly going up, then it's easy to get the longest up-down-up-down sequence. For example, consider 1 5 10 8 3 6:
    We have 1, then 5, which is going up and good, we count length 2 (this counter is r) for now. Then we want to see a number that is smaller than 5, however the 3rd number is 10, we cannot add the length r, but instead we update previous number from 5 to 10 (this number is represented by c), because 10 is the peak but not 5 (at least for now). Then, we want to see a number that is smaller than 10... We keep doing this to find the longest length, in this case, it should be: 1 10 3 6.

    The only issue is we don't know if the mountain is firstly going up or not, this is easy, we just compare first two numbers. I use f, which is either 1 or -1, to control going up or going down for current round.

        def wiggleMaxLength(self, nums):
            if len(nums) <= 1: return len(nums)
            r, c = 1, nums[0]
            f = 1 if nums[1] > nums[0] else -1
            for i in range(1, len(nums)):
                if f*(nums[i] - c) > 0: r, f = r + 1, f*-1
                c = nums[i]
            return r
    

Log in to reply
 

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