LeetCode 376. 摆动序列

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
相似题目

题目描述

✅ 376. 摆动序列

思路分析

解法一：贪心（推荐）

核心思路：

维护 up 表示以上升结尾的摆动长度，down 表示以下降结尾的摆动长度。

若 nums[i] > nums[i-1]，则 up = down + 1。

若 nums[i] < nums[i-1]，则 down = up + 1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }

        int up = 1;
        int down = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }

        return Math.max(up, down);
    }
}

func wiggleMaxLength(nums []int) int {
	if len(nums) < 2 {
		return len(nums)
	}

	up := 1
	down := 1

	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i-1] {
			up = down + 1
		} else if nums[i] < nums[i-1] {
			down = up + 1
		}
	}

	if up > down {
		return up
	}
	return down
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	贪心/DP
376. 摆动序列	中等	贪心
673. 最长递增子序列的个数	中等	DP
1218. 最长定差子序列	中等	DP
1027. 最长等差数列	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/79699960