LeetCode 摆动序列II题解

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是贪心算法的典型应用通过记录上升摆动和下降摆动的数量来计算最长摆动子序列的长度。