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

• 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;
}
``````

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