本文共 1244 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到一个整数数组中最长的摆动子序列的长度。摆动子序列的定义是，相邻元素的差值必须严格交替为正负。

方法思路

我们可以使用动态规划的方法来解决这个问题。具体来说，我们维护两个变量 current_up 和 current_down，分别表示当前以上升或下降结尾的最长子序列长度。初始时，这两个变量都设为1，因为一个单独的元素本身就是一个有效的子序列。

对于每个元素，我们检查它与前一个元素的关系：

• 如果当前元素大于前一个元素，说明当前以上升结尾的子序列长度可以延长为 current_down + 1，而下降结尾的长度保持不变。
• 如果当前元素小于前一个元素，反之，下降结尾的长度延长为 current_up + 1，而上升结尾的长度保持不变。
• 如果当前元素与前一个元素相等，两种状态都不改变。

在每一步中，我们更新最大长度 max_length，确保它始终记录最长的子序列长度。

解决代码

class Solution:    def wiggleMaxLength(self, nums):        if len(nums) <= 1:            return len(nums)        current_up = 1        current_down = 1        max_length = 1        for i in range(1, len(nums)):            if nums[i] > nums[i-1]:                current_up = current_down + 1                current_down = current_down            elif nums[i] < nums[i-1]:                current_down = current_up + 1                current_up = current_up            # else: 当相等时，不改变状态            current_max = max(current_up, current_down)            if current_max > max_length:                max_length = current_max        return max_length

代码解释

• 初始化：检查数组长度，如果小于等于1，直接返回数组长度。
• 循环遍历：从第二个元素开始，逐个检查每个元素与前一个元素的关系。
• 更新状态：根据差值关系，更新 current_up 和 current_down。
• 记录最大值：在每一步更新最大长度 max_length，确保返回最长的摆动子序列长度。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，能够高效地解决问题。

转载地址：http://vkxx.baihongyu.com/