个人主页代码不加冰欢迎来访作者简介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 10000 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 计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - 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]如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。因为我们在计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - 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和第i1个数时代码本质上是在统计由上升/下降所延伸到的终点。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; } }
)
