GuilinDev
Lc0376
05 August 2008
376. Wiggle Subsequence
摆动序列，连续数字之间的差在正数和负数之间交替
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int[] up = new int[len];
int[] down = new int[len];
up[0] = down[0] = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = Math.max(up[i - 1], down[i - 1] + 1);
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[len - 1], down[len - 1]);
}
}
状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int up = 1, down = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > nums[i - 1]) {
up = Math.max(up, down + 1);
} else if (nums[i] < nums[i - 1]) {
down = Math.max(up + 1, down);
}
}
return Math.max(up, down);
}
}
状态压缩的基础上进一步优化，注意到每有一个「峰」到「谷」的下降趋势，\textit{down}down 值才会增加，每有一个「谷」到「峰」的上升趋势，up 值才会增加。且过程中 down 与 up 的差的绝对值值恒不大于 1，即 up <= down≤up + 1，于是有 max(up,down + 1)= down + 1 且max(up+1,down)=up+1。这样可以省去不必要的比较大小的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int up = 1, down = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
贪心，时间O(n)，空间O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int prevdiff = nums[1] - nums[0];
int result = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < len; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
result++;
prevdiff = diff;
}
}
return result;
}
}