LeetCode_94_WiggleSubsequence


1. question: 摆动序列(中等)

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
    子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/wiggle-subsequence

示例 1:

1
2
3
输入:nums = [1,7,4,9,2,5]
输出:6
解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2:

1
2
3
4
输入:nums = [1,17,5,10,13,15,10,5,16,8]
输出:7
解释:这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3:

1
2
输入:nums = [1,2,3,4,5,6,7,8,9]
输出:2

提示:

1
2
1 <= nums.length <= 1000
0 <= nums[i] <= 1000

2. answers

这道题表面上是有那么一点点思路的,但是无法很容易地转换成代码。题目中描述,摆动序列是差值是一正一负,实际上就是一大一小,即某个数的两侧一定要比该数大,某个数的两侧一定要比该数小。为了后续更多的选择,因此,前面的值应该是尽可能大、或者尽可能小。也就是说,作为摆动序列中的值,该值应该尽可能地大,或者尽肯能的小。将原始序列化成折线图,尽可能大的数以及尽可能小的数,只能是极值点。

因此本题,似乎就是求极值点的个数。当前面是递增序列时,突然当前变为递减,那么该点就是极值点;当前面是递减序列时,突然当前变为递增,那么该点就是极值点。对于相等的值,无需考虑(相当于是重合点),继续遍历即可。代码如下所示:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public class Solution_0094 {

public int wiggleMaxLength(int[] nums) {

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

int sums = 0; // 初始化子序列长度为0。
int pre = nums[0]; // 表示要比较的上一个数。

// 为了方便将第一个数加入到序列中,首先判断后续是递增还是递减。
// 如果是后续的数是递减,那么就初始化为递增;
// 如果后续的数是递增,那么就初始化tag为递减。
// 这样,无论是什么情况,第一个数肯定会被加入到子序列中。
boolean tag = true; // true表示当前是递增、false表示当前是递减.

// 首先遍历到两数不等的情况。
int index = 0;
for (int i = 1; i < nums.length; i++) {

if(nums[i] > pre) {
tag = false;
index = i;
break;
} else if(nums[i] < pre) {
tag = true;
index = i;
break;
}
}

// 如果给定的是恒等序列
if(index == 0) return 1;

// 此时index就是下一个要和pre进行比较的数

for (int i = index; i < nums.length; i++) {

// 对于二者相等的情况,直接跳过。
if(nums[i] == pre) continue;

// 本来是递增,但是突然当前值比上一个值小,所以上一个值就是山峰。因此接下来就是递减序列了。
if(tag && nums[i] < pre) {
tag = false;
sums += 1;
}

// 本来是递减,但是突然当前值比上一个值大,所以上一个值就是山谷。因此接下来就是递增序列了。
else if(!tag && nums[i] > pre) {
tag = true;
sums += 1;
}

// 至于其他情况,则完全是递增、递减序列,无需判断,只需要更新pre值即可。
pre = nums[i];
}

// 循环结束,最后一个元素没有添加到序列中(最后一个递增、递减序列还没有添加到序列中;或者说,最后一个极值还没有添加到序列中)。
return sums + 1;

// 上述只是基本情况,但是对于序列中只有一个元素、两个元素(即只有一个序列)的情况需要特殊考虑:
// 对于一个元素的情况,上述其实是满足的;
// 对于两个元素的情况,其实也是满足的。
}

public static void main(String[] args) {

Solution_0094 s = new Solution_0094();

// int[] nums = {1, 7, 4, 9, 2, 5};
// int[] nums = {1,17,5,10,13,15,10,5,16,8};
// int[] nums = {1,2,3,4,5,6,7,8,9};
int[] nums = {33,53,12,64,50,41,45,21,97,35,47,92,39,0,93,55,40,46,69,42,6,95,51,68,72,9,32,84,34,64,6,2,26,98,
3,43,30,60,3,68,82,9,97,19,27,98,99,4,30,96,37,9,78,43,64,4,65,30,84,90,87,64,18,50,60,1,40,32,48,50,
76,100,57,29,63,53,46,57,93,98,42,80,82,9,41,55,69,84,82,79,30,79,18,97,67,23,52,38,74,15};

System.out.println(s.wiggleMaxLength(nums));
}
}

上述是自己在这种思想上实现的代码,有待简化。代码如下所示:

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
28
29
30
31
32
33
34
35
36
public class Solution_0094_02 {

public int wiggleMaxLength(int[] nums) {

if (nums.length <= 1) {
return nums.length;
}

// 当前差值(一定是只有正负时,才可能加入序列;否则不加入)
int curDiff = 0;

// 上一个差值(注意,上一个差值)
int preDiff = 0;

int count = 1;
for (int i = 1; i < nums.length; i++) {

//得到当前差值
curDiff = nums[i] - nums[i - 1];

// 如果当前差值和上一个差值为一正一负
// 等于0的情况表示初始时的preDiff
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {

count++;
preDiff = curDiff;
}
}

return count;
}

public static void main(String[] args) {
System.out.println();
}
}

这道题,重点是能否想到这种思路,求极值点;否则很容易陷入到回溯中(当然回溯也是能够做出来的)。

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录