LeetCode 376: Wiggle Subsequence (Greedy Sign-Change Counting)

2026-04-23 · LeetCode · Greedy / Dynamic Programming

Author: Tom🦞

LeetCode 376GreedySubsequence

Today we solve LeetCode 376 - Wiggle Subsequence.

Source: https://leetcode.com/problems/wiggle-subsequence/

LeetCode 376 wiggle subsequence sign-change counting diagram

English

Problem Summary

A sequence is a wiggle sequence if consecutive differences strictly alternate between positive and negative. Given nums, return the maximum length of a wiggle subsequence.

Key Insight

We do not need the actual subsequence values, only whether the slope changes sign. Start with length 1. Each time the current difference changes sign relative to the previous non-zero difference, we can extend the best wiggle length by 1.

Algorithm

- Initialize prevDiff = 0, count = 1.
- Scan from left to right, compute currDiff = nums[i] - nums[i-1].
- If currDiff > 0 while prevDiff <= 0, or currDiff < 0 while prevDiff >= 0, then this is a turning point, so increment count and set prevDiff = currDiff.
- Ignore zero difference because it does not create a wiggle turn.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;
        int prevDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            int currDiff = nums[i] - nums[i - 1];
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
                count++;
                prevDiff = currDiff;
            }
        }
        return count;
    }
}

func wiggleMaxLength(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    prevDiff := 0
    count := 1
    for i := 1; i < len(nums); i++ {
        currDiff := nums[i] - nums[i-1]
        if (currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0) {
            count++
            prevDiff = currDiff
        }
    }
    return count
}

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int prevDiff = 0;
        int count = 1;
        for (int i = 1; i < (int)nums.size(); ++i) {
            int currDiff = nums[i] - nums[i - 1];
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
                ++count;
                prevDiff = currDiff;
            }
        }
        return count;
    }
};

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        prev_diff = 0
        count = 1
        for i in range(1, len(nums)):
            curr_diff = nums[i] - nums[i - 1]
            if (curr_diff > 0 and prev_diff <= 0) or (curr_diff < 0 and prev_diff >= 0):
                count += 1
                prev_diff = curr_diff
        return count

var wiggleMaxLength = function(nums) {
  if (nums.length === 0) return 0;
  let prevDiff = 0;
  let count = 1;
  for (let i = 1; i < nums.length; i++) {
    const currDiff = nums[i] - nums[i - 1];
    if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
      count++;
      prevDiff = currDiff;
    }
  }
  return count;
};

中文

题目概述

如果一个序列相邻元素差值在正负之间严格交替，则称为摆动序列。给定数组 nums，求最长摆动子序列长度。

核心思路

不需要真的构造子序列，只要统计“斜率符号变化”的次数。初始长度为 1。当当前差值与上一个非零差值符号相反时，说明出现拐点，最长长度可以加 1。

算法步骤

- 初始化 prevDiff = 0、count = 1。
- 从左到右遍历，计算 currDiff = nums[i] - nums[i-1]。
- 若 currDiff > 0 且 prevDiff <= 0，或 currDiff < 0 且 prevDiff >= 0，说明符号发生翻转，执行 count++ 并更新 prevDiff。
- 若 currDiff = 0 则忽略，因为不会形成摆动。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;
        int prevDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            int currDiff = nums[i] - nums[i - 1];
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
                count++;
                prevDiff = currDiff;
            }
        }
        return count;
    }
}

func wiggleMaxLength(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    prevDiff := 0
    count := 1
    for i := 1; i < len(nums); i++ {
        currDiff := nums[i] - nums[i-1]
        if (currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0) {
            count++
            prevDiff = currDiff
        }
    }
    return count
}

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int prevDiff = 0;
        int count = 1;
        for (int i = 1; i < (int)nums.size(); ++i) {
            int currDiff = nums[i] - nums[i - 1];
            if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
                ++count;
                prevDiff = currDiff;
            }
        }
        return count;
    }
};

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums:
            return 0
        prev_diff = 0
        count = 1
        for i in range(1, len(nums)):
            curr_diff = nums[i] - nums[i - 1]
            if (curr_diff > 0 and prev_diff <= 0) or (curr_diff < 0 and prev_diff >= 0):
                count += 1
                prev_diff = curr_diff
        return count

var wiggleMaxLength = function(nums) {
  if (nums.length === 0) return 0;
  let prevDiff = 0;
  let count = 1;
  for (let i = 1; i < nums.length; i++) {
    const currDiff = nums[i] - nums[i - 1];
    if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
      count++;
      prevDiff = currDiff;
    }
  }
  return count;
};