376.摆动数列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

首先判断怎么样才是一个摆动数列，就是差值是正负交替出现的，那么我们是不是可以用一个数组把这些差值全都存储起来，然后根据正负交替的次数来计算最长子序列的长度呢？

是可行的，然后差值数组里只需要判断每个数和前一个数是否异号即可，所以可以边计算便判断。

class Solution376 {
    public int wiggleMaxLength(int[] nums) {
    	if(nums.length < 2) {
    		return nums.length;
    	}else if(nums.length == 2) {
    		if(nums[0] == nums[1]) {
    			return 1;
    		}
    		return 2;
    	}
    	int res = 2;
        //用来判断差值数组里0的数量
    	int differ_0 = 1; 
    	int[] differ = new int[nums.length-1];
    	differ[0] = nums[1] - nums[0];
    	for(int i = 2; i < nums.length; i++) {
            //计算差值并与前一个差值进行比较是否异号
    		differ[i-1] = nums[i] - nums[i-1];
    		if((differ[i-1] * differ[i-2]) < 0) {
    			res++;
                //如果有一个差值等于0,把这个0忽略掉
    		}else if((differ[i-1] * differ[i-2]) == 0) {
    			if(differ[i-1] == 0) {
    				differ[i-1] = differ[i-2];
    			}
    			differ_0 ++;
    		}
    	}
        //如果差值数组全是0,也就是说nums数组里只有一个数,返回1
    	if(differ_0 == differ.length) {
    		return 1;
    	}
    	return res;
    }
}

写完之后运行是0ms,但是我们发现差值数组里每次用到的数看起来都是一样的,是不是可以用两个变量替代呢?因为我们的结果并不需要这个差值数组,所以是可以的.

class Solution376_2 {
    public int wiggleMaxLength(int[] nums) {
    	if(nums.length < 2) {
    		return nums.length;
    	}else if(nums.length == 2) {
    		if(nums[0] == nums[1]) {
    			return 1;
    		}
    		return 2;
    	}
    	int res = 2;
    	int differ_0 = 1;
        //上一个计算的差值
    	int prev = 0;
        //现在计算的差值
    	int cur = 0;
    	prev = nums[1] - nums[0];
    	for(int i = 2; i < nums.length; i++) {
    		cur = nums[i] - nums[i-1];
    		if((cur * prev) < 0) {
    			res++;
    		}else if((cur * prev) == 0) {
    			if(cur == 0) {
    				cur = prev;
    			}
    			differ_0 ++;
    		}
            //每次计算完一次都要更新prev
    		prev = cur;
    	}
    	if(differ_0 == nums.length-1) {
    		return 1;
    	}
    	return res;
    }
}