贪心算法专题(二)：波动中的智慧——只取极值「摆动序列」

哈喽各位，我是前端小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。这种平坡应该被视为单调的一部分，不计入摆动，除非平坡之后方向变了。

算法流程

1. 初始化：

   • curDiff：当前数与后一个数的差值。

   • preDiff：前一对数的差值。

   • result：记录峰谷个数。默认序列最少有一个元素（除非空数组），所以初始为 1（默认把最右边的那个端点算上）。

2. 遍历数组：从0到nums.size() - 2（计算nums[i]和nums[i+1]的差）。

3. 判断拐点：

   • 如果(preDiff <= 0 && curDiff > 0)—— 出现谷。

   • 或者(preDiff >= 0 && curDiff < 0)—— 出现峰。

   • 注意：这里的=是为了处理由平坡变成上下坡的情况（如1-1-2，中间的1算谷底）。

4. 更新状态：

   • 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)，但逻辑比贪心复杂）。

总结：贪心的“视觉化”

今天这道题，如果只看数字，很容易被“平坡”、“删除元素”绕晕。 但如果把它想象成**“山脉图”**，贪心策略就显而易见了：我们只想要山顶和谷底，山腰上的石头全扔掉！

这就是贪心算法的魅力——通过忽略中间过程（单调区间），直接抓住关键变化（转折点）。

下一题预告： 如果我们在一个数组中寻找**“和最大”的连续子数组**（最大子序和），贪心算法该如何操作？ 策略很简单：如果当前的累加和变成了负数，它对未来不仅没有贡献，还是个累赘，那我们就果断抛弃它，从头开始算！

下期见！