Count the turning points, No DP No Greedy


  • 0
    Y

    Inspired by this post: https://discuss.leetcode.com/topic/52179/o-n-solution-no-code
    I don't use DP or Greedy algorithm.
    2 steps:

    1. remove the duplicates in the array, in place.
    2. count the turning points of the array
    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length == 0 || nums == null) return 0;
            if (nums.length == 1 ) return 1;
            //remove duplicates in array, in-place
            int i = 1, j;
            for ( j = 1; j < nums.length; j++) {
                if(nums[j] != nums[j-1]) nums[i++] = nums[j];  
            }
    
            // i is the length of array after removing duplicates
            if (i == 1) return 1;
            if ( i == 2) return 2;
            int count = 0;
            for (int i1 = 1 ; i1 <= i-2; i1++) {
                if((nums[i1]-nums[i1-1])*(nums[i1+1]-nums[i1]) < 0) {
                    count++;
                }
            }
            
            return count+2;
        }    
    }
    

Log in to reply
 

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