leetcode Wiggle Subsequence

leetcode Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,[1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Follow up:
Can you do it in O(n) time?

题目地址:leetcode Wiggle Subsequencey

题意:给定一个数组,让你求最大摆动序列长度。摆动序列定义为序列中任意相邻的三个数中abc,均有 a < b , b >c 或者a>b b<c

思路:

方法一,看到这个就想到和LIS差不多,迅速的DP一下,1A,

设dp[i] 为以i结尾的最大摆动序列长度,sign[i]为i这个数比之前的大还是小(大为1,小-1,初始0),更新条件如下:

  • dp[j] + 1 > dp[i] and (sign[j] > 0 and nums[i] < nums[j] or sign[j] < 0 and nums[i] > nums[j] or sign[j] == 0 and nums[i] != nums[j]):

很好的写出相应的python code:

 

方法二 虽然dp简单,但其复杂度O(n^2)并不是本题最佳解法。

摇摆序列要求升高,降低,升高。。。

或者降低,升高,降低。。。

那么我们只要找出数组中的“拐点” 即可 举个例子:

4 5 6  3 2 1这几个数中,4为起点,那么5和6中,我们肯定选6啊~因为之后的数要求小于5,小于5的必定也小于6 比如改为4 5 6 5,之前要是选5就没办法继续往下了。。

总之就是选最小的和选最大的(也就是拐点) 保证不丢最优解。

C++

Java

Python

 

本题是leetcode 376 Wiggle Subsequence题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Wiggle Subsequence
本文地址:https://www.hrwhisper.me/leetcode-wiggle-subsequence/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

7 thoughts on “leetcode Wiggle Subsequence

  1. dp的解法条件里 是不是应该短路成 ( !sign[j] && sign[i] != sign[j] ) 好呢,不然如果是[ 1,1,1,1…] 相等的情况就会是 2 了。

  2. 有个问题想请教下,我用第二种思路写的代码,死活有两个用例过不去。。。对比了一下你的代码,感觉没什么区别。。。大神有时间能帮忙看一下么,代码在下面贴出来了。

    • 不知道怎么回事,代码贴上去就错了。。。我又看了下,貌似是我最后的else不该加上去,应该在内层的while循环里面把等于的循环条件加上去,就不会报错。可是这有什么区别吗。。。没看出来啊。。。

        • 多谢多谢。。。我考虑了等于的情况,不过没写对。。。比如可能是小于-等于-小于这样的情况,然后按我的算法就加了两次。。。非常感谢

Leave a Reply

Your email address will not be published. Required fields are marked *