网站制作图书网站建设营销外包公司排名

1. 题目：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [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

2. 我的代码：

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:# -- 贪心算法 --# 双指针p_fast = 1p_slow = 0# 快慢指针result = 0while p_fast < len(nums) - 1:p_fast += 1if nums[p_fast - 1] > nums[p_fast] and nums[p_fast - 1] > nums[p_slow]:k = 1result += 1p_slow = p_fast - 1elif nums[p_fast - 1] < nums[p_fast] and nums[p_fast - 1] < nums[p_slow]:k = -1result += 1p_slow = p_fast - 1if len(nums) > 2:if nums[0] != nums[len(nums) - 1]:endPoint = 2else:if result == 0:endPoint = 1else:endPoint = 2else:if nums[0] != nums[len(nums) - 1]:endPoint = 2else:endPoint = 1return result + endPoint

这里使用贪心算法，局部的极值就是要求得的摆动点。首先因为要返回一个值即可，所以不需要实际地去将列表做删减，只需要统计整个过程中的摆动点的个数即可，变为数学问题就是求极值点的个数。什么是极值点来着，用数学的定义就是在小区间内，这个点最大就是极大值，这个点最小就是极小值。

因此，我们设置快慢指针，分别表示要判断的点的右边的点和左边的点。那么中间要判断的点就是快指针的后一位，为什么呢。假设[1, 2, 3, 1]这样的序列。慢指针在[1]，快指针在[3]，这时要判断的点是[2]，因为[2]并不比[1]和[3]都大，所以2不是极值点。因为后面要变大的点一定比[1]大，所以，可以保留慢指针在这个位置，要判断的值和快指针一起向前走即可。

再加上两个端点处的摆动点即可（如果整个序列只有一个元素，则是一个摆动点；如果序列元素是2个，但是两个值相同，则摆动点还是一个；如果两个值不相同，则摆动点是2个）…

端点判断代码如下（有点长，但是时间复杂度不高）：

if len(nums) > 2:if nums[0] != nums[len(nums) - 1]:endPoint = 2else:if result == 0:endPoint = 1else:endPoint = 2
else:if nums[0] != nums[len(nums) - 1]:endPoint = 2else:endPoint = 1

小结：

关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||代码兼职|| ||代码问题求解||
添加我的公众号即可：