Really Simple Idea: remove duplicates and find peaks!!!


  • 0
    W

    We can easily prove that only by picking the peak elements and elements at both ends can we achieve the longest wiggle subsequence. So the idea is really simple.

    • Remove duplicated elements
    • Find the peak elements.

    O(n) time, O(n) space

    int wiggleMaxLength(vector<int>& nums) {
            vector<int> unique;
            for(int i = 1; i < nums.size(); i++) {
                if(nums[i] == nums[i-1]) continue;
                else unique.push_back(nums[i-1]);
            }
            if(!nums.empty())unique.push_back(nums.back());
            if(unique.size() <= 2) return min(1, (int)unique.size()); 
            int count = 0;
            for(int i = 1; i < unique.size()-1; i++) {
                if(unique[i-1] < unique[i] && unique[i] > unique[i+1]) count++;
                else if(unique[i-1] > unique[i] && unique[i] < unique[i+1]) count++;
            }
            return count + 2;
        }
    

    O(n) time, O(1) space.

    int wiggleMaxLength(vector<int>& nums) {
            int tail = 0, iter = 0, n = nums.size();
            for(; iter < n; iter++) {
                if(nums[iter] != nums[tail])
                    nums[++tail] = nums[iter];
            }
            if(tail+1 <= 2) return min(1, (int)nums.size()); 
            int count = 0;
            for(int i = 1; i < tail; i++) {
                if(nums[i-1] < nums[i] && nums[i] > nums[i+1]) count++;
                else if(nums[i-1] > nums[i] && nums[i] < nums[i+1]) count++;
            }
            return count + 2;
        }
    

Log in to reply
 

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