：波动中的智慧——只取极值「摆动序列」)
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第二篇！ 什么是“摆动”？简单说就是一上一下。比如[1, 7, 4, 9, 2, 5]，差值是+6, -3, +5, -7, +3，正负交替，这就是摆动序列。 而[1, 4, 7, 9]单调递增，或者[1, 1, 1]平的，都不是摆动。
我们的任务是：给你一个数组，你可以随意删除里面的元素（也就是求子序列），剩下的元素必须构成一个摆动序列。请问最长能剩多少个？
力扣 376. 摆动序列
https://leetcode.cn/problems/wiggle-subsequence/
题目分析：
输入：整数数组
nums。目标：最长摆动子序列的长度。
例子：
[1, 17, 5, 10, 13, 15, 10, 5, 16, 8]整个数组显然不是摆动的（比如
10, 13, 15连着涨）。我们可以删掉
13，保留10, 15，就变成了...10, 15, 10...（一上一下）。实际上，我们只需要保留所有的“峰”和“谷”，删掉所有在半山腰上的点。
核心思维：忽略“平坡”，只数“峰谷”
想象把你手里的数组画成一张折线图。
摆动的本质就是折线的拐点。
如果连续上升
1 -> 2 -> 3 -> 4，这是一条直线上坡。为了构成摆动，我们只需要保留起点1和终点4。中间的2和3都可以删掉，因为它们没有改变趋势。
贪心策略：我们只需要统计数组中**“峰”（Peak）和“谷”（Valley）**的数量。
峰：数值先升后降。即
preDiff > 0且curDiff < 0。谷：数值先降后升。即
preDiff < 0且curDiff > 0。平坡处理：这是难点！比如
1 -> 2 -> 2 -> 2 -> 3。这种平坡应该被视为单调的一部分，不计入摆动，除非平坡之后方向变了。
算法流程
初始化：
curDiff：当前数与后一个数的差值。preDiff：前一对数的差值。result：记录峰谷个数。默认序列最少有一个元素（除非空数组），所以初始为 1（默认把最右边的那个端点算上）。
遍历数组：从
0到nums.size() - 2（计算nums[i]和nums[i+1]的差）。判断拐点：
如果
(preDiff <= 0 && curDiff > 0)—— 出现谷。或者
(preDiff >= 0 && curDiff < 0)—— 出现峰。注意：这里的
=是为了处理由平坡变成上下坡的情况（如1-1-2，中间的1算谷底）。
更新状态：
result++。preDiff = curDiff。关键点：只有在出现摆动变化的时候，才更新preDiff。这样可以自动过滤掉单调区间内的平坡。
代码实现 (C++)
C++
#include <vector> using namespace std; class Solution { public: int wiggleMaxLength(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); int curDiff = 0; // 当前一对元素的差值 int preDiff = 0; // 前一对元素的差值 int result = 1; // 记录峰值个数，默认最后一个元素算一个峰值 for (int i = 0; i < nums.size() - 1; i++) { curDiff = nums[i + 1] - nums[i]; // 出现峰或谷 // preDiff <= 0 && curDiff > 0 : 之前是平或降，现在升了（谷） // preDiff >= 0 && curDiff < 0 : 之前是平或升，现在降了（峰） if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) { result++; // 关键细节：只在摆动变化的时候更新 preDiff // 这样能处理单调区间中有平坡的情况，如 1->2->2->2->3 // preDiff 会一直保持为正，直到遇到下降 preDiff = curDiff; } } return result; } };深度复杂度分析
时间复杂度：O(N)
我们只需要遍历一次数组。
空间复杂度：O(1)
只需要几个变量记录差值和结果。
相比之下，动态规划解法通常需要两个数组
up[N]和down[N]，空间复杂度为O(N)（虽然可以优化到 O(1)，但逻辑比贪心复杂）。
总结：贪心的“视觉化”
今天这道题，如果只看数字，很容易被“平坡”、“删除元素”绕晕。 但如果把它想象成**“山脉图”**，贪心策略就显而易见了：我们只想要山顶和谷底，山腰上的石头全扔掉！
这就是贪心算法的魅力——通过忽略中间过程（单调区间），直接抓住关键变化（转折点）。
下一题预告： 如果我们在一个数组中寻找**“和最大”的连续子数组**（最大子序和），贪心算法该如何操作？ 策略很简单：如果当前的累加和变成了负数，它对未来不仅没有贡献，还是个累赘，那我们就果断抛弃它，从头开始算！
下期见！
