题目描述：

LeetCode 376题 Wiggle Subsequence（摆动序列）要求我们找到一个序列的最长摆动子序列的长度。摆动序列的定义是：序列中的元素在相邻元素之间交替上升和下降。

题目示例：

输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列就是一个摆动序列。

输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 序列中的最长摆动子序列是 [1,17,10,13,10,16,8]。

解题思路：

我们可以使用贪心算法来解决这个问题。具体思路如下：

1. 初始化： 定义两个变量 up 和 down，分别表示当前序列中上升和下降的最长摆动子序列的长度。初始时都设为1，因为任何一个单独的元素都可以看作是一个摆动序列。
2. 遍历序列： 从第二个元素开始遍历整个序列，对于每一个元素，根据它与前一个元素的关系来更新 up 和 down：
   • 如果当前元素大于前一个元素，说明这是一个上升的过程，此时 up 应该更新为 down + 1，因为上升序列可以接在之前的下降序列后面。
   • 如果当前元素小于前一个元素，说明这是一个下降的过程，此时 down 应该更新为 up + 1，因为下降序列可以接在之前的上升序列后面。
3. 结果： 遍历完成后，up 和 down 中的最大值就是最长摆动子序列的长度。

代码实现（Python）：

def wiggleMaxLength(nums): if not nums: return 0 up = down = 1 for i in range(1, len(nums)): if nums[i] > nums[i - 1]: up = down + 1 elif nums[i] < nums[i - 1]: down = up + 1 return max(up, down)

print(wiggleMaxLength([1,7,4,9,2,5])) # 输出: 6 print(wiggleMaxLength([1,17,5,10,13,15,10,5,16,8])) # 输出: 7

复杂度分析：

• 时间复杂度： O(n)，其中 n 是序列的长度。我们只需要遍历一次序列。
• 空间复杂度： O(1)，我们只使用了常数级别的额外空间。

总结：

这个题目通过贪心算法可以高效解决，关键在于正确理解和维护上升和下降序列的长度。通过简单的遍历和更新操作，我们能够在线性时间内找到最长摆动子序列的长度。这种方法不仅简洁，而且效率高，适合处理大规模数据。