O(n) Java solution with comment


  • 0
    S

    The basic idea is to find the number of removed numbers.

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums == null || nums.length == 0)
                return 0;
            
            int delete_num = 0, pre = 0, idx;
            for (idx = 1; idx < nums.length; idx++) {
                if (nums[idx] == nums[pre]) {
                    // not wiggle, remove nums[pre]
                    delete_num++;
                    pre = idx;
                } else if (nums[pre] < nums[idx]) {
                    if (idx == nums.length -1 || nums[idx] > nums[idx+1])
                        // wiggle, move next
                        pre = idx;
                    else
                        // not wiggle, remove nums[idx]
                        delete_num++;
                } else {
                    // nums[pre] > nums[idx]
                    if (idx == nums.length -1 || nums[idx] < nums[idx+1])
                        // wiggle, move next
                        pre = idx;
                    else
                        // not wiggle, remove nums[idx]
                        delete_num++;
                }
            }
            return nums.length - delete_num;
        }
    }
    

Log in to reply
 

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