【LeetCode刷题日记】贪心算法：376摆动序列-拓冰建站

🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记，苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家后，我是代码不加冰，今天依旧是下了一上午的雨，可能中午就出来大太阳了，这天气真是有点折磨人，不扯那么多了，直接进入到我们的每日刷题环节。

摘要：

本文介绍了LeetCode 376题"摆动序列"的解题思路。摆动序列要求相邻数字差值正负交替出现。核心解法采用贪心算法，时间复杂度O(n)，空间复杂度O(1)。关键思路是统计序列中的峰谷点，因为选择极值点能最大化后续选择空间。文中详细分析了三种特殊情况处理：平坡、首尾元素和单调坡中的平坡。最终给出的Java代码通过比较当前差值和前一个差值的变化来统计摆动次数，初始计数为1以包含首元素。该解法高效地找出最长摆动子序列长度。

题目背景：376.摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如，[1, 7, 4, 9, 2, 5]是一个摆动序列，因为差值(6, -3, 5, -7, 3)是正负交替出现的。
相反，[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组nums，返回nums中作为摆动序列的最长子序列的长度。
示例 1：
输入：nums = [1,7,4,9,2,5]输出：6解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]输出：7解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]输出：2
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
进阶：你能否用O(n)时间复杂度完成此题?

题目解析：

这道题是经典的贪心算法。时间复杂度为 O(n)，空间复杂度为 O(1)。

核心解题思路

我们可以把数组想象成一个起伏的折线图。所谓的“摆动”，实际上就是折线图中的峰（局部极大值）和谷（局部极小值）。

如果我们在上升段，我们希望尽可能走到最顶端（峰）；
如果我们在下降段，我们希望尽可能走到最底端（谷）。

因此，我们只需要统计这个折线图中有多少个峰和谷即可，因为即便我们不统计峰谷，随意选一个递增或者递减之间的元素，对于结果来说也是没有影响的。但是为什么我们这里写的是峰谷呢

重点注意：

结论是我们可以选，但选峰和谷能为我们留出最大的退路，保证后面能接到更多的数。
贪心算法的本质是走一步看一步，且每一步都选当下最好的。在这一题里，选“峰”和“谷”就是能让后面的选择空间达到最大的“最优解”。
我们通过一个具体的例子来看看，为什么选中间的元素会吃亏：
假设有一段单调递增的序列：[1, 3, 5, 9]，后面紧跟着一个2。整个序列是：[1, 3, 5, 9, 2]。
现在我们在上升阶段，面临选择。我们的目标是：选完这个数之后，希望下一个数比它小（因为要形成摆动）。
策略 A（贪心：选峰顶 9）：我们选择了9。现在序列是[1, 9]。接下来遇到了2。因为2 < 9，成功形成下降，序列变成[1, 9, 2]，长度为3。
策略 B（选中间的元素 3 或者 5）：如果我们选了中间的5。现在序列是[1, 5]。接下来遇到了2。因为2 < 5，也能形成下降，序列变成[1, 5, 2]，长度也是3。看起来没区别
但是，如果后面的数不是 2，而是 7 呢，也就是序列变成了：[1, 3, 5, 9, 7]。
策略 A（选峰顶 9）：序列[1, 9]，接下来遇到7。因为7 < 9，满足下降！成功接上，变成[1, 9, 7]，长度为3。
策略 B（选中间的元素 5）：序列[1, 5]，接下来遇到7。可是7比5大，它无法形成下降趋势，7就被浪费掉了。最终长度只能卡在2（即[1, 5]或[1, 7]）。
核心逻辑
当你在上升时：越往上走，数字越大。数字越大，后面能小于它的概率就越高（也就是越容易遇到比它小的数，从而形成下坡）。所以我们要贪心地一路走到峰顶。
当你在下降时：越往下走，数字越小。数字越小，后面能大于它的概率就越高（也就是越容易遇到比它大的数，从而形成上坡）。所以我们要贪心地一路走到谷底。
选择中间的元素，实际上是自己窄化了未来的路。只有选择峰和谷，才能保证我们的序列在面对后续未知的数字时，有更多的选择。

解决完这个，本题也算是完成一半了，下面就是具体的代码逻辑。

代码逻辑

在计算是否有峰值的时候，大家知道遍历的下标 i ，计算 prediff（nums[i] - nums[i-1]）和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0或者prediff > 0 && curdiff < 0此时就有波动就需要统计。

这是我们思考本题的一个大体思路，但本题要考虑三种情况：

情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡

情况一：上下坡中有平坡

在图中，当 i 指向第一个 2 的时候，prediff > 0 && curdiff = 0，当 i 指向最后一个 2 的时候prediff = 0 && curdiff < 0。
如果我们采用，删左面三个 2 的规则，那么当prediff = 0 && curdiff < 0也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。
所以我们记录峰值的条件应该是：(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)，为什么这里允许 prediff == 0 ，就是为了上面说的这种情况。
所以本题统计峰值的时候，数组最左面和最右面如何统计呢？
题目中说了，如果只有两个不同的元素，那摆动序列也是 2。
例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算 prediff（nums[i] - nums[i-1]）和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。
这里我们可以写死，就是如果只有两个元素，且元素不同，那么结果为 2。
不写死的话，如何和我们的判断规则结合在一起呢？
可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？
之前我们在讨论情况一：相同数字连续的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。
那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：
针对以上情形，result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）

统计的是转折点，而转折点 = 边界数 - 1

通过代码会发现，我们是在for循环里去寻找峰顶和谷底。当出现转折时，count++。
我们拿一个简单的递增数组[1, 2, 3]来举例：
1 到 2 是上升趋势（curDiff > 0,predDiff == 0），触发count++。
2 到 3 还是上升趋势（curDiff > 0,predDiff > 0），不触发count++。
循环结束。
此时，代码里只在1到2的时候加了 1 次，如果count初始是 0，最后结果就是 1。但实际上[1, 2, 3]最长摆动子序列长度是 2（比如[1, 2]或[1, 3]）。
为什么少算了 1，因为我们在看第i和第i+1个数时，代码本质上是在统计由上升/下降所延伸到的终点。
1 -> 2上升，我们把2算作一个有效的转折点（count变 2）。
而序列的第一个数字（也就是1），在它前面没有任何数字与它作比较，所以循环里永远不会把它算进去。
总结：初始的count = 1，实际上代表的就是序列的第一个元素（或者最右边的最后一个边界）。我们先把它预留出来，后续循环里只要每找到一次方向的切换（峰或谷），再往上累加即可。

题目答案：

class Solution { public int wiggleMaxLength(int[] nums) { if (nums.length <= 1) { return nums.length; } //当前差值 int curDiff = 0; //上一个差值 int preDiff = 0; int count = 1; for (int i = 1; i < nums.length; i++) { //得到当前差值 curDiff = nums[i] - nums[i - 1]; //如果当前差值和上一个差值为一正一负 //等于0的情况表示初始时的preDiff if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) { count++; preDiff = curDiff; } } return count; } }