376. Wiggle Subsequence

https://leetcode.com/problems/wiggle-subsequence/

solution

• 注意这里的判断条件

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:        
        if len(nums) < 2:
            return len(nums)
        
        pre = 0
        res = 1
        for i in range(1, len(nums)):
            diff = nums[i] - nums[i-1]

            if pre * diff <= 0 and diff != 0:
                res += 1
                pre = diff
        return res

时间复杂度：O() 空间复杂度：O()

follow up

*280. Wiggle Sort

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        # 1. If i is even, then nums[i] <= nums[i - 1].
        # 2. If i is odd, then nums[i] >= nums[i - 1].
        for i in range(1, len(nums)):
            if i & 1 == 0 and nums[i] > nums[i - 1] or i & 1 == 1 and nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]    

时间复杂度：O(n) 空间复杂度：O(1)

324. Wiggle Sort II

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        arr = sorted(nums)
        for i in range(1, len(nums), 2):
            nums[i] = arr.pop()
        for i in range(0, len(nums), 2):
            nums[i] = arr.pop()

• 结合 n-largest 与 wiggle sort I 的方法