376. 摆动序列

题目链接：https://leetcode-cn.com/problems/wiggle-subsequence/

示例

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

• 差值为{16,-12,5,3,2,-5,11,-8}

• 循环与前一个值比较，遇到相同符号的数一起合并，遇到相反符号数时序列长度增加，修改前一个值。

• leetcode题解为动态规划和贪心解法

执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35.8 MB, 在所有 Java 提交中击败了80.28% 的用户

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length == 1) {
            return 1;
        }
        int len = 1;
        int n = nums.length;
        boolean zero = true;
        int[] diff = new int[n-1];
        for(int i = 1; i < n; i++) {
            diff[i-1] = nums[i] - nums[i-1];
            // 判断是否都为相同值
            if (zero && diff[i-1] != 0) {
                zero = false;
            }
        }
        if (zero) {
            return 1;
        }
        int last = diff[0];
        for(int i = 1; i < n-1; i++) {
            if (diff[i] > 0 && last < 0) {
                len++;
                last = diff[i];
            } else if(diff[i] < 0 && last > 0) {
                len++;
                last = diff[i];
            } else {
                last += diff[i];
            }
        }
        return len+1;
    }
}