[leetcode]376. Wiggle Subsequence -- JavaScript代码-蒲公英云

[leetcode]376. Wiggle Subsequence -- JavaScript代码

Myth丶恋晨 2022-09-24 06:21 213阅读 0赞

这道题目的要求是：
给定一个数组，要求不改变元素顺序，从这个数组里找到一个最长子数组，该子数组中的元素要求一大一小的依次排列。返回值就是这个最长子数组的长度。

这道题给的标签是DP和贪心算法。

PS：代码效率不算很高，欢迎大家改进指正。

JavaScript代码如下：

/** * @param {number[]} nums * @return {number} */
var wiggleMaxLength = function(nums) {
    var wiggle = [];
    if(nums.length===0){
        return 0;
    }
    if(nums.length==1){
        return 1;
    }
    if(nums[0]>nums[1]){
        high = nums[0];
        low = nums[1];
        flag = 0;// 0表示需要升高，1表示需要下降
    }else if(nums[0]<nums[1]){
        high = nums[1];
        low = nums[0];
        flag = 1;// 0表示需要升高，1表示需要下降
    }else{
        high = low = nums[0];
        wiggle.push(nums[0]);
        flag = 2;// 2表示未知
    }
    nums.forEach(function(item){
        if(flag===0){
            if(item>low){
                high = item;
                wiggle.push(item);
                flag = 1;
            }else if(item<low){
                low = item;
                wiggle.pop();
                wiggle.push(item);
            }
        }else if(flag==1){
            if(item<high){
   // 需要下降
                low = item;
                wiggle.push(item);
                flag = 0;
            }else if(item>high){
                high = item;
                wiggle.pop();
                wiggle.push(item);
            }
        }else{
            if(item>low){
                flag = 0;
            }else if(item<high){
                flag = 1;
            }
        }
    });
    return wiggle.length;
};