广东省水利工程建设信息网站,网站gif图标素材,ppt模板免费下载 素材红色主题,长沙律师网站建设摆动序列
Leetcode 376
学习记录自代码随想录
如果连续数字之间的差严格地在正数和负数之间交替#xff0c;则数字序列称为 摆动序列 。第一个差#xff08;如果存在的话#xff09;可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如#…摆动序列
Leetcode 376
学习记录自代码随想录
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。
给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1 输入nums [1,7,4,9,2,5] 输出6 解释整个序列均为摆动序列各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2 输入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 输入nums [1,2,3,4,5,6,7,8,9] 输出2
要点1.计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]如果prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计 2.统计波动即峰值点数则所求序列总长度为峰值点数加1所以序列长度默认值设为1 3.nums.size() 2不等的情况其实已经在下面涉及到了在数组长度为2时在之前加一个点和nums[0]相同即可并入下面的情况 3.1nums.size() 3(preDiff 0 curDiff 0) || (preDiff 0 curDiff 0) 2在数组长度为2时在之前加一个点和nums[0]相同即可并入之前的情况用该条件(preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)判断3如果把prediff curdiff放在for大循环中则每次都更新会将下面这种情况错记录进去所以应该在峰值点出现时再更新prediff curdiff
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size() 1) return nums.size();// if(nums.size() 2 nums[0] nums[1]){// return 1;// }else if(nums.size() 2 nums[0] ! nums[1]){// return nums.size();// } // nums.size() 2不等的情况其实已经在下面涉及到了在数组长度为2时在之前加一个点和nums[0]相同即可并入下面的情况int max_len 1; // 默认为1因为统计的是峰值点所以总长度为峰值点数加1int prediff 0;int curdiff 0;for(int i 0; i nums.size()-1; i){curdiff nums[i1] - nums[i];if((prediff 0 curdiff 0) || (prediff 0 curdiff 0)){max_len; // 峰值点的累加prediff curdiff; // 峰值点出现后再更新}}return max_len; }
};
