0376-摆动序列(0376 swing sequence)-其他

0376-摆动序列(0376 swing sequence)

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

• https://leetcode-cn.com/problems/wiggle-subsequence/solution/376-bai-dong-xu-lie-tan-xin-jing-dian-ti-vyxt/

python

``````# 0376.摆动序列

class Solution:
def wiggleMaxLength(self, nums: [int]) -> int:
"""
贪心算法，摆动序列，波动区间，保持锯齿向前伸展(自创)
preDiff, curDiff表示当前数值与前个元素的差值及当前数值与后一个元素的差值
在不断遍历中，只有当preDiff及curDiff异号时，说明当前元素是局部波峰波谷，此时res++
当元素个数为1时，不进入循环，直接返回res的初始值，仅当nums长度大于等于2时，才进入for loop
:param nums:
:return:
"""
preDiff, curDiff, res = 0, 0, 1
for i in range(len(nums)-1):
curDiff = nums[i+1] - nums[i]
if preDiff*curDiff <= 0 and curDiff != 0:
res += 1
preDiff = curDiff
return res
``````

goalng

``````package greedy

// 贪心算法-保持锯齿向前伸展
func wiggleMaxLength(nums []int) int {
var count, preDiff, curDiff int
count = 1
if len(nums) < 2 {
return count
}
for i:=0;i<len(nums)-1;i++ {
curDiff = nums[i+1] - nums[i]
if curDiff*preDiff <= 0 && curDiff != 0 {
preDiff = curDiff
count++
}
}
return count
}

``````
————————

If the difference between consecutive numbers strictly alternates between positive and negative numbers, the number sequence is called a swing sequence. The first difference (if any) may be positive or negative. A sequence with only one element or two unequal elements is also regarded as a swing sequence.

• For example,   [1, 7, 4, 9, 2, 5] is a swing sequence because of the difference (6, – 3, 5, – 7, 3)   It is alternating positive and negative.
• Conversely, [1, 4, 7, 2, 5]   and   [1, 7, 4, 5, 5] is not a swing sequence. The first sequence is because its first two differences are positive, and the second sequence is because its last difference is zero.
Subsequences can be obtained by deleting some (or no) elements from the original sequence, and the remaining elements maintain their original order.

Give you an integer array nums, which returns the length of the longest subsequence of the swing sequence in nums.

Example 1:

Input: num = [1,7,4,9,2,5]
Output: 6
Explanation: the whole sequence is a swing sequence, and the difference between each element is (6, – 3, 5, – 7, 3).
Example 2:

Input: num = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: this sequence contains several swing sequences with a length of 7.
One of them is [1, 17, 10, 13, 10, 16, 8], and the difference between the elements is (16, – 7, 3, – 3, 6, – 8).
Example 3:

Input: num = [1,2,3,4,5,6,7,8,9]
Output: 2

Tips:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Advanced: can you use it   O (n) time complexity to complete this question?

reference resources:

• https://leetcode-cn.com/problems/wiggle-subsequence/solution/376-bai-dong-xu-lie-tan-xin-jing-dian-ti-vyxt/

python

``````# 0376.摆动序列

class Solution:
def wiggleMaxLength(self, nums: [int]) -> int:
"""
贪心算法，摆动序列，波动区间，保持锯齿向前伸展(自创)
preDiff, curDiff表示当前数值与前个元素的差值及当前数值与后一个元素的差值
在不断遍历中，只有当preDiff及curDiff异号时，说明当前元素是局部波峰波谷，此时res++
当元素个数为1时，不进入循环，直接返回res的初始值，仅当nums长度大于等于2时，才进入for loop
:param nums:
:return:
"""
preDiff, curDiff, res = 0, 0, 1
for i in range(len(nums)-1):
curDiff = nums[i+1] - nums[i]
if preDiff*curDiff <= 0 and curDiff != 0:
res += 1
preDiff = curDiff
return res
``````

goalng

``````package greedy

// 贪心算法-保持锯齿向前伸展
func wiggleMaxLength(nums []int) int {
var count, preDiff, curDiff int
count = 1
if len(nums) < 2 {
return count
}
for i:=0;i<len(nums)-1;i++ {
curDiff = nums[i+1] - nums[i]
if curDiff*preDiff <= 0 && curDiff != 0 {
preDiff = curDiff
count++
}
}
return count
}

``````