376. Wiggle Subsequence

  • 34.9%

https://leetcode.com/problems/wiggle-subsequence/

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

1
2
3
4
5
6
7
8
9
10
11
12
> Examples:
> Input: [1,7,4,9,2,5]
> Output: 6
> The entire sequence is a wiggle sequence.
>
> Input: [1,17,5,10,13,15,10,5,16,8]
> Output: 7
> There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
>
> Input: [1,2,3,4,5,6,7,8,9]
> Output: 2
>

Follow up:

Can you do it in O(n) time?

java

0ms, September 11, 2016

https://discuss.leetcode.com/topic/51946/very-simple-java-solution-with-detail-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length < 2) return nums.length;

int k = 0;
while(k < nums.length - 1 && nums[k] == nums[k+1]) k++;

if(k == nums.length - 1) return 1;

int result = 2;
boolean smallReq = nums[k] < nums[k+1];
for(int i = k+1; i<nums.length-1; i++){
if(smallReq && nums[i+1] < nums[i]){
// nums[result] = nums[i+1];
result++;
smallReq = !smallReq;
}else{
if(!smallReq && nums[i+1] > nums[i]){
// nums[result] = nums[i+1];
result++;
smallReq = !smallReq;
}
}
}
return result;
}
}

cpp

0ms, September 11, 2016

https://discuss.leetcode.com/topic/51893/two-solutions-one-is-dp-the-other-is-greedy-8-lines

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size = nums.size(), f=1, d=1;
for(int i=1; i<size; ++i){
if(nums[i]>nums[i-1]) f=d+1;
else if(nums[i]<nums[i-1]) d=f+1;
}
return min(size, max(f,d));
}
};

13ms, September 11, 2016

https://discuss.leetcode.com/topic/51893/two-solutions-one-is-dp-the-other-is-greedy-8-lines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size=nums.size();
if(size==0) return 0;
vector<int> f(size, 1);
vector<int> d(size, 1);
for(int i=1; i<size; ++i){
for(int j=0; j<i; ++j){
if(nums[j]<nums[i]){
f[i]=max(f[i], d[j]+1);
}
else if(nums[j]>nums[i]){
d[i]=max(d[i], f[j]+1);
}
}
}
return max(d.back(), f.back());
}
};
谢谢你,可爱的朋友。