企业官网建设流程全解析

LeetCode 376. 摆动序列

题目分析

摆动序列要求相邻差值正负交替。关键思路：贪心——只需要统计序列中"峰"和"谷"的数量。

· 每当出现一个"趋势转折点"（峰或谷），摆动长度 +1
· 用 prediff 记录上一次的差值符号，curdiff 记录当前差值符号
· 只有当 prediff 和 curdiff 异号（或 prediff == 0）时才算一个转折

Java 实现

classSolution{publicintwiggleMaxLength(int[]nums){if(nums.length<=1)returnnums.length;intcount=1;// 至少有一个元素intprediff=0;// 前一个差值intcurdiff=0;// 当前差值for(inti=1;i<nums.length;i++){curdiff=nums[i]-nums[i-1];// 出现峰值或谷值if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0)){count++;prediff=curdiff;}}returncount;}}

代码详解

核心判断条件：

if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0))

· prediff <= 0 && curdiff > 0：从"下降/平"变为"上升" → 谷值
· prediff >= 0 && curdiff < 0：从"上升/平"变为"下降" → 峰值
· 使用 <= / >= 而不是 < / >，可以自动跳过平坡（如 [1,1,1,2] 中的连续相等元素）

为什么 prediff 只在转折时才更新？

如果每次都更新 prediff = curdiff，那么平坡情况（如 [1,2,2,2,1]）会导致漏判。只在转折时更新可以跳过平坡上的中间点。

样例追踪

以 nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8] 为例：

i nums[i] curdiff prediff 是否转折 count
1 17 +16 0 是 2
2 5 -12 +16 是 3
3 10 +5 -12 是 4
4 13 +3 +5 否 4
5 15 +2 +5 否 4
6 10 -5 +5 是 5
7 5 -5 -5 否 5
8 16 +11 -5 是 6
9 8 -8 +11 是 7

结果：7

复杂度分析

· 时间复杂度：O(n)，一次遍历
· 空间复杂度：O(1)，只用了常数个变量

扩展：动态规划解法

如果面试官追问，可以用 DP：

classSolution{publicintwiggleMaxLength(int[]nums){if(nums.length<2)returnnums.length;intup=1,down=1;// up: 以当前元素结尾且最后趋势向上的最长摆动长度for(inti=1;i<nums.length;i++){if(nums[i]>nums[i-1]){up=down+1;}elseif(nums[i]<nums[i-1]){down=up+1;}}returnMath.max(up,down);}}

这个 DP 更简洁，本质和贪心一致，面试时可以先说贪心思路，再用这个作为备选。