摆动序列

难度:中等

摆动序列

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

例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3)是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

描述:

给定一个整数序列,返回作为摆动序列的最长子序列的长度

通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

样例:

示例1:

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。
1
2
3

示例2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]
1
2
3

示例3:

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

思路分析:

  1. 整数序列可以删除
  2. 序列要不断上升和下降才有效。

代码模板:

const wiggleMaxLength = function (nums) {
}
1
2

代码:

  1. 缓存上次的摆动方向, 只关注下一个正确的摆动方向。

当方向正确序列的长度就可以增加了,中间的连续上升/下降不用管。

const wiggleMaxLength = function (nums) {
    if (nums.length < 2) {
        return nums.length; // 小于2 直接返回
    }
    let length = 1; // 默认每个数字为1
    let flag = "begin"; // 初始摆动方向
    for (var i = 0; i < nums.length - 1; i++) {
        switch (flag) {
            case "begin":
                if (nums[i] < nums[i + 1]) {
                    flag = "up"; // 摆动方向
                    length++; // 初始两个值为摆动序列
                } else if (nums[i] > nums[i + 1]) {
                    flag = "down";
                    length++; // 初始两个值为摆动序列
                }
                break;
            case "up":
                if (nums[i] > nums[i + 1]) {
                    // 找到下一组下一个值比本身小的值
                    flag = "down";
                    length++;
                }
                break;
            case "down":
                if (nums[i] < nums[i + 1]) {
                    // 找到下一组下一个值比本身大的值
                    flag = "up";
                    length++;
                }
                break;
        }
    }
    return length;
}
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
  1. 将上升和下降视为一组,当正确摆动过一次(上升和下降各出现一次)时,序列的长度+1。

连续摆动因为另一个变量没有变化,所以就会得到相同的结果,相当于跳过。

const wiggleMaxLength = function (nums) {
    let len = nums.length
    if (len < 2) return len // 小于2 返回它本身的长度 大于2的数量 进入比较
    let up = 1
    let down = 1
    for (let 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)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

鼓励我一下:

觉得还不错的话,给我的项目点个star

点个Star支持我一下~

最后更新时间: 10/31/2019, 9:11:01 PM