欢迎阅读 欢迎来到「摆动序列」题解之旅本文将带你从“寻找最长上下交替的子序列”这一序列处理问题出发深入理解贪心算法与状态机的巧妙结合并掌握如何通过统计波峰波谷的数量快速得到最长摆动序列的长度。在开始之前建议你先了解题目背景这是 LeetCode 376 题给定整数数组nums要求删除一些元素也可不删后得到最长的摆动子序列即相邻差值严格正负交替。明确学习目标掌握两种主流解法贪心法统计峰谷数量和动态规划维护上升/下降状态的最长长度理解它们各自的思路和适用场景并熟练处理相等元素的跳过逻辑。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,17,5,10,13,15,10,5,16,8]输出7。本文将从问题转化、贪心策略峰谷统计、动态规划状态机、代码实现到复杂度分析层层递进。即使你对贪心和 DP 还不熟悉我们也会从“画出折线图找拐点”这一直观角度出发让你轻松抓住核心思想——摆动序列的长度就是波浪中波峰波谷的总数。现在让我们一起在数字的起伏中寻找最长的摆动轨迹吧 一、题目376. 摆动序列 - 力扣LeetCode二、做题思路1. 问题分析前置分析摆动序列要求相邻元素的差值严格正负交替。要得到最长摆动子序列只需保留所有符号发生变化的转折点即波峰或波谷而忽略中间单调连续的部分。因为每个转折点都能贡献一个摆动最终长度 转折点个数 1首尾元素。2. 贪心策略核心决策规则从左到右遍历数组计算每对相邻元素的差值right nums[i1] - nums[i]。若right 0直接跳过相等元素不影响摆动。维护一个变量left记录上一次非零差值的符号。当right与left符号相反或left 0时即right * left 0则出现一个转折点计数ret。更新left right继续向后遍历。3. 正确性说明简单版本在一个单调递增或递减的区间内只有首尾两个端点对摆动有贡献中间的连续元素只会产生相同符号的差值不会增加摆动长度。因此我们只需统计差值符号发生变化的次数每次变化都对应一个波峰或波谷保留这些转折点就能得到最长的摆动子序列。贪心策略每次遇到转折就计入跳过无关的中间点最终得到的长度就是全局最优解。4. 实现细节边界防护如果数组长度 2直接返回n单元素或空数组本身就是摆动序列。初始化left 0表示无方向ret 0。遍历中跳过right 0避免改变方向。使用right * left 0判断符号变化注意乘法可能溢出但本题数值范围小安全。最后返回ret 1。5. 返回值目标映射返回ret 1即最长摆动子序列的长度。三、代码class Solution { public: int wiggleMaxLength(vectorint nums) { int n nums.size(); // 边界处理如果数组长度小于2则整个数组本身就是摆动序列 if (n 2) { return n; } // 贪心策略统计“峰”或“谷”的个数相邻差值符号发生变化时长度1。 // 具体只统计符号发生变化的转折点忽略中间连续递增或递减的中间元素。 int ret 0; // 统计符号发生变化的次数即峰/谷的个数 int left 0; // 前一对元素的差值nums[i] - nums[i-1]初始为0表示无方向 // 遍历相邻元素对从 i0 到 n-2即比较 nums[i] 和 nums[i1] for (int i 0; i n - 1; i) { int right nums[i 1] - nums[i]; // 当前相邻差值 // 跳过差值为0的情况即相等元素不改变方向 if (right 0) { continue; } // 如果当前差值与上一个差值符号相反或上一个为0则出现一个转折点 // left * right 0 表示符号不同包含左为0的情况 if (right * left 0) { ret; // 统计这个转折点 } // 更新左差值为当前差值用于下次比较 left right; } // 转折点个数 1 摆动序列的长度因为首尾元素也算入长度 return ret 1; } };四、流程图五、正确性说明详细版步骤 1符号与问题建模---------------------------------------------------- | 输入数组 nums长度 n | | 定义相邻差值d[i] nums[i1] - nums[i] | | 摆动序列要求相邻差值正负交替严格交替 | | 单个或两个不等元素也视为摆动序列 | ---------------------------------------------------- | v ---------------------------------------------------- | 贪心策略统计“转折点”峰/谷数量 | | 具体操作从左到右扫描相邻差值 | | 每当差值符号发生变化或从0变为非0 | | 就计为一个转折点最终长度 转折点数 1 | | 忽略中间连续递增/递减的元素只保留端点 | ----------------------------------------------------设left存储上一个差值初始为 0表示尚未确定方向。当扫描到right nums[i1] - nums[i]时若right 0跳过相等元素不改变方向也不产生转折。否则若left * right 0则说明left 0这是第一个非零差值确立了初始摆动方向应计为转折。left与right异号方向发生反转出现一个极值点。每次计满后更新left right。贪心本质在每一个单调区间连续上升或下降中只保留两端的极值点即转折点删除中间所有点这样既保持摆动性质又不减少长度。步骤 2关键性质 —— 分类讨论与反证法证明转折点的有效性---------------------------------------------------- | 情况 1连续递增段 x1 x2 ... xk | | 最优子序列在该段最多取两个端点极小值、极大值 | | 中间点取与不取都不会增加长度反而可能破坏摆动 | | 反证若取了中间点则相邻差同号不满足摆动。 | ---------------------------------------------------- | v ---------------------------------------------------- | 情况 2连续递减段 x1 x2 ... xk | | 同理只保留两端的极大值和极小值 | ---------------------------------------------------- | v ---------------------------------------------------- | 情况 3相等元素差值为0 | | 跳过因为差值为0会导致摆动中断 | ----------------------------------------------------详细论证结合反证与分类讨论反证法假设在一个严格单调的区间内最优摆动子序列取了三个或更多点。由于它们是单调的任意相邻三个点之间的差值符号相同全正或全负这违反摆动序列定义。因此最优解中任何一个单调区间内最多只能取两个端点即一个极小值和一个极大值。分类讨论递增区间nums[i] nums[i1] ...可取左端点局部极小和右端点局部极大中间点全部删除长度不减少且摆动性保持。递减区间同理可取左端点局部极大和右端点局部极小。相等元素差值为0不产生符号变化删除它们可使摆动更连续。贪心选择性质从左到右扫描每当遇到差值符号变化即新的极值点就将其纳入摆动序列。这种“只保留转折点”的策略能保证在每个单调段只取两端从而得到最长的可能长度。步骤 3归纳证明 —— 全局最优性通过交换论证---------------------------------------------------- | 从左到右构建摆动序列 | | 当前已选序列末尾符号为 sign正或负 | | 遇到一个新的极值点符号变化就追加到末尾 | | 若符号未变继续单调则跳过中间点 | ---------------------------------------------------- | v ---------------------------------------------------- | 交换论证假设存在最优解其第一个转折点位置为 p | | 而贪心选择的位置为 q可能更早或更晚。 | | 可以证明将最优解中的转折点替换为贪心选取的转折点 | | 不改变后续可用的极值点集合且长度不变或更大。 | ---------------------------------------------------- | v ---------------------------------------------------- | 结论贪心统计的转折点数 1 即为最长摆动子序列长度 | ----------------------------------------------------详细论证由步骤2每个单调区间最多贡献两个点一个峰一个谷因此整个序列的最长摆动子序列长度等于“转折点峰谷的个数 1”首尾计入。归纳证明考虑从左到右处理数组维护当前已选择的最后一个差值符号。每当新出现的差值符号与之前不同时这个新位置必然是一个极值点转折贪心将其纳入序列。这个选择不会使后续可选的极值点减少因为后续的极值点出现在更后面与当前极值点的选择无关。交换论证图片中提及若最优解在某处选择了非转折点则它必定可以替换为该段内的转折点而不损失长度因为替换后仍能保持摆动且不改变后续符号交替情况。经过若干次交换最优解可转化为贪心解。因此贪心扫描得到的转折点数就是最大可能的极值个数从而ret 1即为所求最长摆动子序列长度。 闭幕 恭喜你完成了「摆动序列」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题采用贪心策略只统计相邻差值符号发生变化的转折点峰或谷忽略中间连续递增或递减的元素。为什么这样能保证得到最长摆动子序列你能用[1,2,3,4]举例说明为什么不统计中间元素依然能得到正确长度吗代码中用left记录上一对元素的差值符号用right记录当前差值。当right * left 0时认为是转折点。为什么条件是 0而不是 0如果left0时right*0 0恒成立这会带来什么影响延伸挑战如果题目改为求最长连续摆动子数组子数组要求连续而不是子序列解法应该怎么改只需要修改哪部分如果数组元素可以是负数差值符号的判断仍然有效吗代码需要调整吗如果要求输出最长摆动子序列的具体元素不只是长度你如何在贪心过程中记录路径如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
LeetCode 376：摆动序列（贪心算法）—— 题解
欢迎阅读 欢迎来到「摆动序列」题解之旅本文将带你从“寻找最长上下交替的子序列”这一序列处理问题出发深入理解贪心算法与状态机的巧妙结合并掌握如何通过统计波峰波谷的数量快速得到最长摆动序列的长度。在开始之前建议你先了解题目背景这是 LeetCode 376 题给定整数数组nums要求删除一些元素也可不删后得到最长的摆动子序列即相邻差值严格正负交替。明确学习目标掌握两种主流解法贪心法统计峰谷数量和动态规划维护上升/下降状态的最长长度理解它们各自的思路和适用场景并熟练处理相等元素的跳过逻辑。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,17,5,10,13,15,10,5,16,8]输出7。本文将从问题转化、贪心策略峰谷统计、动态规划状态机、代码实现到复杂度分析层层递进。即使你对贪心和 DP 还不熟悉我们也会从“画出折线图找拐点”这一直观角度出发让你轻松抓住核心思想——摆动序列的长度就是波浪中波峰波谷的总数。现在让我们一起在数字的起伏中寻找最长的摆动轨迹吧 一、题目376. 摆动序列 - 力扣LeetCode二、做题思路1. 问题分析前置分析摆动序列要求相邻元素的差值严格正负交替。要得到最长摆动子序列只需保留所有符号发生变化的转折点即波峰或波谷而忽略中间单调连续的部分。因为每个转折点都能贡献一个摆动最终长度 转折点个数 1首尾元素。2. 贪心策略核心决策规则从左到右遍历数组计算每对相邻元素的差值right nums[i1] - nums[i]。若right 0直接跳过相等元素不影响摆动。维护一个变量left记录上一次非零差值的符号。当right与left符号相反或left 0时即right * left 0则出现一个转折点计数ret。更新left right继续向后遍历。3. 正确性说明简单版本在一个单调递增或递减的区间内只有首尾两个端点对摆动有贡献中间的连续元素只会产生相同符号的差值不会增加摆动长度。因此我们只需统计差值符号发生变化的次数每次变化都对应一个波峰或波谷保留这些转折点就能得到最长的摆动子序列。贪心策略每次遇到转折就计入跳过无关的中间点最终得到的长度就是全局最优解。4. 实现细节边界防护如果数组长度 2直接返回n单元素或空数组本身就是摆动序列。初始化left 0表示无方向ret 0。遍历中跳过right 0避免改变方向。使用right * left 0判断符号变化注意乘法可能溢出但本题数值范围小安全。最后返回ret 1。5. 返回值目标映射返回ret 1即最长摆动子序列的长度。三、代码class Solution { public: int wiggleMaxLength(vectorint nums) { int n nums.size(); // 边界处理如果数组长度小于2则整个数组本身就是摆动序列 if (n 2) { return n; } // 贪心策略统计“峰”或“谷”的个数相邻差值符号发生变化时长度1。 // 具体只统计符号发生变化的转折点忽略中间连续递增或递减的中间元素。 int ret 0; // 统计符号发生变化的次数即峰/谷的个数 int left 0; // 前一对元素的差值nums[i] - nums[i-1]初始为0表示无方向 // 遍历相邻元素对从 i0 到 n-2即比较 nums[i] 和 nums[i1] for (int i 0; i n - 1; i) { int right nums[i 1] - nums[i]; // 当前相邻差值 // 跳过差值为0的情况即相等元素不改变方向 if (right 0) { continue; } // 如果当前差值与上一个差值符号相反或上一个为0则出现一个转折点 // left * right 0 表示符号不同包含左为0的情况 if (right * left 0) { ret; // 统计这个转折点 } // 更新左差值为当前差值用于下次比较 left right; } // 转折点个数 1 摆动序列的长度因为首尾元素也算入长度 return ret 1; } };四、流程图五、正确性说明详细版步骤 1符号与问题建模---------------------------------------------------- | 输入数组 nums长度 n | | 定义相邻差值d[i] nums[i1] - nums[i] | | 摆动序列要求相邻差值正负交替严格交替 | | 单个或两个不等元素也视为摆动序列 | ---------------------------------------------------- | v ---------------------------------------------------- | 贪心策略统计“转折点”峰/谷数量 | | 具体操作从左到右扫描相邻差值 | | 每当差值符号发生变化或从0变为非0 | | 就计为一个转折点最终长度 转折点数 1 | | 忽略中间连续递增/递减的元素只保留端点 | ----------------------------------------------------设left存储上一个差值初始为 0表示尚未确定方向。当扫描到right nums[i1] - nums[i]时若right 0跳过相等元素不改变方向也不产生转折。否则若left * right 0则说明left 0这是第一个非零差值确立了初始摆动方向应计为转折。left与right异号方向发生反转出现一个极值点。每次计满后更新left right。贪心本质在每一个单调区间连续上升或下降中只保留两端的极值点即转折点删除中间所有点这样既保持摆动性质又不减少长度。步骤 2关键性质 —— 分类讨论与反证法证明转折点的有效性---------------------------------------------------- | 情况 1连续递增段 x1 x2 ... xk | | 最优子序列在该段最多取两个端点极小值、极大值 | | 中间点取与不取都不会增加长度反而可能破坏摆动 | | 反证若取了中间点则相邻差同号不满足摆动。 | ---------------------------------------------------- | v ---------------------------------------------------- | 情况 2连续递减段 x1 x2 ... xk | | 同理只保留两端的极大值和极小值 | ---------------------------------------------------- | v ---------------------------------------------------- | 情况 3相等元素差值为0 | | 跳过因为差值为0会导致摆动中断 | ----------------------------------------------------详细论证结合反证与分类讨论反证法假设在一个严格单调的区间内最优摆动子序列取了三个或更多点。由于它们是单调的任意相邻三个点之间的差值符号相同全正或全负这违反摆动序列定义。因此最优解中任何一个单调区间内最多只能取两个端点即一个极小值和一个极大值。分类讨论递增区间nums[i] nums[i1] ...可取左端点局部极小和右端点局部极大中间点全部删除长度不减少且摆动性保持。递减区间同理可取左端点局部极大和右端点局部极小。相等元素差值为0不产生符号变化删除它们可使摆动更连续。贪心选择性质从左到右扫描每当遇到差值符号变化即新的极值点就将其纳入摆动序列。这种“只保留转折点”的策略能保证在每个单调段只取两端从而得到最长的可能长度。步骤 3归纳证明 —— 全局最优性通过交换论证---------------------------------------------------- | 从左到右构建摆动序列 | | 当前已选序列末尾符号为 sign正或负 | | 遇到一个新的极值点符号变化就追加到末尾 | | 若符号未变继续单调则跳过中间点 | ---------------------------------------------------- | v ---------------------------------------------------- | 交换论证假设存在最优解其第一个转折点位置为 p | | 而贪心选择的位置为 q可能更早或更晚。 | | 可以证明将最优解中的转折点替换为贪心选取的转折点 | | 不改变后续可用的极值点集合且长度不变或更大。 | ---------------------------------------------------- | v ---------------------------------------------------- | 结论贪心统计的转折点数 1 即为最长摆动子序列长度 | ----------------------------------------------------详细论证由步骤2每个单调区间最多贡献两个点一个峰一个谷因此整个序列的最长摆动子序列长度等于“转折点峰谷的个数 1”首尾计入。归纳证明考虑从左到右处理数组维护当前已选择的最后一个差值符号。每当新出现的差值符号与之前不同时这个新位置必然是一个极值点转折贪心将其纳入序列。这个选择不会使后续可选的极值点减少因为后续的极值点出现在更后面与当前极值点的选择无关。交换论证图片中提及若最优解在某处选择了非转折点则它必定可以替换为该段内的转折点而不损失长度因为替换后仍能保持摆动且不改变后续符号交替情况。经过若干次交换最优解可转化为贪心解。因此贪心扫描得到的转折点数就是最大可能的极值个数从而ret 1即为所求最长摆动子序列长度。 闭幕 恭喜你完成了「摆动序列」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题采用贪心策略只统计相邻差值符号发生变化的转折点峰或谷忽略中间连续递增或递减的元素。为什么这样能保证得到最长摆动子序列你能用[1,2,3,4]举例说明为什么不统计中间元素依然能得到正确长度吗代码中用left记录上一对元素的差值符号用right记录当前差值。当right * left 0时认为是转折点。为什么条件是 0而不是 0如果left0时right*0 0恒成立这会带来什么影响延伸挑战如果题目改为求最长连续摆动子数组子数组要求连续而不是子序列解法应该怎么改只需要修改哪部分如果数组元素可以是负数差值符号的判断仍然有效吗代码需要调整吗如果要求输出最长摆动子序列的具体元素不只是长度你如何在贪心过程中记录路径如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
