376. 摆动序列(Wiggle Subsequence)
描述
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
思路
贪心。首先,如果它不为空,那么序列长度至少会是一。序列中相邻元素的关系只有四种:相等、递增、递减、增减摆动(题目中要求的情况)。
- 首先如果是相等,那么是不影响的因为当前元素和前一个元素相等,那么和后面元素的差也是相等的,直接跳过即可;
- 递增或者递减。以递增为例,如果是递增,那么永远保存最大的那个数,因为如果小数字可以和后面的数字构成摆动序列的话,大数字一定可以,因为当前是递增的,摆动序列中该数的下一个数一定小于该数。即:a<b,那么 a 一定小于 x ( x > b )举例
3,4,7,5,6
。 - 增减摆动,就是判断上一次的运算结果和当前运算结果异或结果是否为 true,是的话摆动序列元素加一。
根据这些关系,当一个数和保存的前一个数(不一定是相邻的)之差 和上一次的差点结果不同时,即可判断当前元素属于百摆动序列。
解答
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) return nums.length;
int cnt = 1;
int tmp = nums[1];
boolean flag = true;//第一次
boolean zf = false;//上一次的正负 true ~ 正, false ~ 负
for (int i = 1; i < nums.length; i++) {
if (flag) {
if (nums[i] - nums[i - 1] != 0) {
cnt++;
zf = nums[i] - nums[i - 1] > 0;
flag = false;
tmp = nums[i];
}
}
else {
if (nums[i] - tmp== 0)continue;
boolean test = nums[i] - tmp > 0;
//异号
// 异或不是与
if ((test ^ zf)){
cnt++;
zf = test;
}
tmp= nums[i];
}
}
return cnt;
}
}