贪心与堆中等1 种解法

#376摆动序列

从数组中删除若干元素，使相邻差值严格正负交替，求最长摆动子序列长度。

#数组#贪心#动态规划

解题主线

连续同向变化时只需保留最有利的峰或谷，中间点不会增加摆动次数。

当前差值与上一个有效差值异号时才出现新的峰谷；初始差值为 0 可统一处理第一次非零变化。

相等元素形成平坡，既不增加长度，也不应覆盖上一个有效方向。

解法 1：峰谷贪心

扫描相邻差值，仅当方向从非正转正或从非负转负时计入一个新的摆动点，并更新有效方向。

时间复杂度

O(n)

空间复杂度

O(1)

376. 摆动序列 · 峰谷贪心

java

final class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int length = 1;
        long previousDifference = 0;
        for (int i = 1; i < nums.length; i++) {
            long currentDifference = (long) nums[i] - nums[i - 1];
            boolean turnsUp = currentDifference > 0 && previousDifference <= 0;
            boolean turnsDown = currentDifference < 0 && previousDifference >= 0;
            if (turnsUp || turnsDown) {
                length++;
                previousDifference = currentDifference;
            }
        }
        return length;
    }
}

扫描相邻差值，仅当方向从非正转正或从非负转负时计入一个新的摆动点，并更新有效方向。

边界与易错点

摆动要求差值严格为正或负，相邻相等不能计数。
长度为 0 或 1 的数组答案就是自身长度。
直接用 int 相减在极端整数输入下可能溢出，使用 long 保存差值更稳妥。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q376_wiggleMaxLength.java