A very simple O(n) C solution


  • 0
    M
    int wiggleMaxLength(int* nums, int numsSize) {
        int i = 0;
        int diff = 0;
        int p_diff = 0;
        int n_diff = 0;
        int no_diff = 0;
        int count = 0;
        if(numsSize == 1)
            return 1;
        if(numsSize == 0)
            return 0;    
        while(i < numsSize - 1)
        {
            diff = nums[i+1] - nums[i];
            
            if(diff > 0)
            {
                n_diff = 0;
                if(p_diff == 0) count++;
                p_diff++;
                i++;
            }
            else if(diff < 0)
            {
                p_diff = 0;
                if(n_diff == 0) count++;
                i++;
                n_diff++;
            }
            else 
            {
                i++;
                no_diff++;
            }
        }
        return count+1;
    }
    

    C solution above uses a simple principle.

    We pick the first of the positive diff in a set of continuous positive diffs and we select the last of the negative diffs in a set of continuous negative diffs. For a zero diff, we simply go to next. Feel free to provide your feedback! :)


Log in to reply
 

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