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] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
    子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 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) 时间复杂度完成此题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/wiggle-subsequence

参考:

  • 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?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/wiggle-subsequence

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
}