当前位置：首页 > news >正文

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

news 2026/7/15 17:31:26

哈喽各位，我是前端小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; } };