LeetCode 摆动序列II题解
题目描述
给定一个整数序列，如果连续数字之间的差严格地交替正负，则称该序列为摆动序列。返回最长摆动子序列的长度。
示例：
输入：nums = [1,7,4,9,2,5]
输出：6
解题思路
方法：贪心
思路：
- 使用贪心算法，记录上升摆动和下降摆动的数量。
- 遍历数组，计算摆动的次数。
- 当遇到连续相同差值时，只计算一次摆动。
复杂度分析：
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
代码实现
def wiggle_max_length(nums): if len(nums) < 2: return len(nums) 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) # 测试 def test_wiggle_max_length(): nums = [1, 7, 4, 9, 2, 5] print(wiggle_max_length(nums)) # 输出：6 if __name__ == "__main__": test_wiggle_max_length()总结
摆动序列II是贪心算法的典型应用，通过记录上升摆动和下降摆动的数量来计算最长摆动子序列的长度。
