摆动序列
摆动序列
一、问题描述
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 中作为摆动序列的最长子序列的长度。
二、解题思路
摆动序列的关键在于寻找数组中的峰和谷。每当序列发生方向变化时，摆动序列的长度就会增加。因此，可以通过遍历数组，统计方向变化的次数来得到最长摆动序列的长度。
- 记录初始趋势：计算数组前两个元素的差值作为最开始的变化趋势preTrend = nums[1] - nums[0]，若差值不为 0，说明前两个元素构成了摆动序列的初始趋势，此时摆动序列长度初始化为 2；若差值为 0，意味着前两个元素相等，不构成摆动趋势，摆动序列长度初始化为 1。
- 遍历数组寻找变化趋势：记录当前变化趋势curTrend = nums[i] - nums[i - 1]，若当前变化趋势curTrend 与之前的变化趋势preTrend 不同，preTrend <= 0 && curTrend > 0 或者 preTrend >= 0 && curTrend < 0 时 更新变化趋势preTrend ，摆动序列加1
三、代码实现
以下是使用 JavaScript 实现的代码：
var wiggleMaxLength = function (nums) {
// 统计波峰波谷的数量
// 若长度为1 或为 0
if (nums.length < 2) return nums.length;
let preTrend = nums[1] - nums[0];
let reLen = preTrend !== 0 ? 2 : 1;
for (let i = 2; i < nums.length; i++) {
let curTrend = nums[i] - nums[i - 1];
// 当出现波谷或者波峰时，更新preTrend
if ((preTrend <= 0 && curTrend > 0) || (preTrend >= 0 && curTrend < 0)) {
preTrend = curTrend;
reLen++;
}
}
return reLen;
};
四、注意事项
- 边界条件需谨慎：在处理数组前两个元素确定初始趋势时，要特别注意数组长度为 2 的情况。若两个元素相等，初始化摆动序列长度为 1，此时不能因为后续没有更多元素判断趋势变化，就错误认为长度还能增加。在遍历过程中，若遇到数组结尾，也应保证最后一次趋势变化能正确统计，避免遗漏。
- 趋势判断避免误判：在比较差值判断趋势变化时，条件 (preTrend <= 0 && curTrend > 0) 与 (preTrend >= 0 && curTrend < 0) 中的 “小于等于” 和 “大于等于” 不能随意替换为 “小于” 和 “大于”。例如，当出现连续相等元素后趋势改变的情况，若使用严格的 “小于” 和 “大于” 判断，可能会错过第一个有效趋势变化点，导致结果错误。
五、复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历一次数组。
- 空间复杂度：O(1)，只需要常数级的额外空间。
作者：G等你下课
来源：juejin.cn/post/7518198430662492223
来源：juejin.cn/post/7518198430662492223
