C++, 3ms, O(n) time, O(1) space, greedy solution


  • 0
    V
    class Solution {
    public:
        
        int wiggleMaxLength(vector<int>& nums) {
            int n=nums.size();
            if(n<=1)
                return n;
            
            int index=0;
            while(index<n-1) //handling duplicate entries
            {
                if(nums[index]==nums[index+1])
                    index++;
                else
                    break;           
            }
            if(index>=n-1)
                return 1;
            
            bool pre=(nums[index]<nums[index+1]);
            int len=2;        
            
            for(int i=index+1; i<n-1;i++)
            {
                // using last sign and current direc for validation
                if(pre^(nums[i]<nums[i+1]) && nums[i]!=nums[i+1]) 
                {
                    len++;
                    pre=!pre;
                }
            }
            return len;        
        }
    };
    
    

Log in to reply
 

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