1. question: 摆动序列(中等)
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/wiggle-subsequence
示例 1:
1 | 输入:nums = [1,7,4,9,2,5] |
示例 2:
1 | 输入:nums = [1,17,5,10,13,15,10,5,16,8] |
示例 3:
1 | 输入:nums = [1,2,3,4,5,6,7,8,9] |
提示:
1 | 1 <= nums.length <= 1000 |
2. answers
这道题表面上是有那么一点点思路的,但是无法很容易地转换成代码。题目中描述,摆动序列是差值是一正一负,实际上就是一大一小,即某个数的两侧一定要比该数大,某个数的两侧一定要比该数小。为了后续更多的选择,因此,前面的值应该是尽可能大、或者尽可能小。也就是说,作为摆动序列中的值,该值应该尽可能地大,或者尽肯能的小。将原始序列化成折线图,尽可能大的数以及尽可能小的数,只能是极值点。
因此本题,似乎就是求极值点的个数。当前面是递增序列时,突然当前变为递减,那么该点就是极值点;当前面是递减序列时,突然当前变为递增,那么该点就是极值点。对于相等的值,无需考虑(相当于是重合点),继续遍历即可。代码如下所示:
1 | public class Solution_0094 { |
上述是自己在这种思想上实现的代码,有待简化。代码如下所示:
1 | public class Solution_0094_02 { |
这道题,重点是能否想到这种思路,求极值点;否则很容易陷入到回溯中(当然回溯也是能够做出来的)。
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。