首页 > 代码库 > 376. Wiggle Subsequence
376. Wiggle Subsequence
不定期更新leetcode解题java答案。
采用pick one的方式选择题目。
题意为给定数组，获取满足要求的最长子串的长度。要求为前后两个数字差为绝对的正负关系（差为0不满足要求）。
例如，[1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) 。
7-1=6>0, 4-7=-3<0， 9-4=5>0， 2-9=-7<0, 5-2=3>0。
采用贪心算法先获取两相邻数的差，再进行判断是否满足正负关系。试想若两个连续的差均为大于0的数，例如[2,1,3,5,...]，则选取的留下数组有[2,1,3,...]和[2,1,5,...]。
显然后者更佳（容易满足题意），由此可得出如下代码：
1 public class Solution { 2 public int wiggleMaxLength(int[] nums) { 3 if(nums.length == 0) 4 return 0; 5 6 int[] differences = new int[nums.length - 1]; 7 8 for(int i = 0; i < differences.length; i++) 9 differences[i] = nums[i + 1] - nums[i];10 11 int count = 1;12 int lastValue = http://www.mamicode.com/0;13 int difference = 0;14 for(int i = 0; i < differences.length; i++){15 difference = differences[i]; //get difference value16 17 if(lastValue =http://www.mamicode.com/= 0){18 if(difference != 0){19 lastValue = http://www.mamicode.com/difference > 0 ? 1 : -1;20 count++;21 }22 }else{23 if(difference * lastValue < 0){24 lastValue = http://www.mamicode.com/lastValue > 0 ? -1 : 1;25 count++;26 }27 } 28 }29 30 return count;31 }32 }
376. Wiggle Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。