Greedy Java solution. O(n) time and O(1) space complexity.


  • 0
    O
    public int wiggleMaxLength(int[] nums) {
        	if(nums.length == 0) return 0;
        	if(nums.length == 1) return 1;
        	int prev = nums[0], current = nums[1], sign = 0, step = 2;
        	sign = prev < current ? 1 : (prev > current ? -1 : 0);
        	for(int i = 2; i < nums.length && sign == 0; i++) {
        		sign = current < nums[i] ? 1 : (current > nums[i] ? -1 : 0);
        		if (sign != 0) current = nums[i];
        		step++;
        	}
        	if (sign == 0) return 1;
        	int result = 2;
        	for(int i = step; i < nums.length; i++) {
        		if(current < nums[i] && sign < 0) {
        			sign = 1;
        			prev = current;
        			current = nums[i];
        			result++;
        		} else if (current > nums[i] && sign > 0) {
        			sign = -1;
        			prev = current;
        			current = nums[i];
        			result++;
        		} else if(prev < nums[i] && sign > 0) {
        			current = nums[i];
        		} else if (prev > nums[i] && sign < 0) {
        			current = nums[i];
        		}
        	}
            return result;
        }
    

Log in to reply
 

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