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
进阶:
你能否用 O(n) 时间复杂度完成此题?
题解
对于一个数组，求出其最长的摆动子序列的长度。
不需要对数组进行处理，使其求出最长摆动数组的同时，自身变为摆动数组。
1、问题转化——问题可以转变为求一个数组，它的变化率是间隔变化的。
- 就是一个求图形中有多少个单调性转折点的问题
- 代码
// java
class Solution {
final static boolean UP = true;
final static boolean DOWN = false;
public int wiggleMaxLength(int[] nums) {
// 长度小于 2, 直接返回0
if (nums.length < 2) {
return nums.length;
}
int len = 1;
int diff;
boolean first = true,oriention = UP;
// 求相邻项之差，从而进行判断
for (int i = 1;i < nums.length;i++) {
diff = nums[i] - nums[i - 1];
if (first){
// 处理第一个元素
if (diff != 0) {// 前两个数字不等
len++;
if (diff > 0){ // 第一组为上升
oriention = DOWN;// 下一组下降
}else{ // 第一组下降
oriention = UP;// 下一组上升
}
first = false;
}
} else {
// 需要一个正值
if (oriention) {
if (diff > 0) {
len++;
oriention = DOWN;
}
}else{ // 需要一个负值
if (diff < 0) {
len++;
oriention = UP;
}
}
}
}
return len;
}
}
// 优化一下代码实现--官方所谓的贪心算法
// 空间优化，实现优化
class Solution{
public int miggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int diff,prediff = nums[1] - nums[0];
// 初始化摆动数组的长度
int count = prediff != 0? 2:1;
for (int i = 2;i < nums.length;i++) {
diff = nums[i] - nums[i-1];
// prediff 加等号是因为数组的前两个数字可能相等
if ((diff > 0 && prediff <= 0) || (diff < 0 && prediff >= 0)) {
count++;
prediff = diff;
}
}
return diff;
}
}
// 借助switch
class Solution {
public int wiggleMaxLength(int[] nums) {
final int BEGIN = 0;
final int UP = 1;
final int DOWN = 2;
int count = 1;
int state = BEGIN;
if(nums.length < 2){
return nums.length;
}
for (int i = 1; i < nums.length; i++) {
switch (state){
case BEGIN:
if(nums[i] > nums[i - 1]){
state = UP;
++count;
}else if(nums[i] < nums[i - 1]){
state = DOWN;
++count;
}
continue;// 直接进行下一个循环
case UP:
if(nums[i] < nums[i - 1]){
++count;
state = DOWN;
}
continue;
case DOWN:
if(nums[i] > nums[i - 1]){
++count;
state = UP;
}
continue;
}
}
return count;
}
}
2、暴力求解
- 利用递归思想，全局搜索
public class Solution {
/**
nums: 原数组
index: 当前遍历的下标
isUp: 目标状态
*/
private int calculate(int[] nums, int index, boolean isUp) {
int maxcount = 0;
// 深度优先遍历
for (int i = index + 1; i < nums.length; i++) {
// 要么需要递增、要么递减
if ((isUp && nums[i] > nums[index]) || (!isUp && nums[i] < nums[index]))
// 递归求解摆动子数组的长度
maxcount = Math.max(maxcount, 1 + calculate(nums, i, !isUp));
}
return maxcount;
}
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2)
return nums.length;
return 1 + Math.max(calculate(nums, 0, true), calculate(nums, 0, false));
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode/
3、动态规划
两个数组：
up[i]存的是目前为止最长的以第 i 个元素结尾的上升摆动序列的长度。down[i]记录的是目前为止最长的以第 i 个元素结尾的下降摆动序列的长度。
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2)
return nums.length;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
// 遍历数组
for (int i = 1; i < nums.length; i++) {
// 遍历已有的dp状态数组，更新最大的长度
for(int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
up[i] = Math.max(up[i],down[j] + 1);
} else if (nums[i] < nums[j]) {
down[i] = Math.max(down[i],up[j] + 1);
}
}
}
return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode/
线性动态规划
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2)
return nums.length;
int[] up = new int[nums.length];//记录递增个数
int[] down = new int[nums.length];//记录递减个数
up[0] = down[0] = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {// 递增
up[i] = down[i - 1] + 1;// 由递减加 1
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {// 递减
down[i] = up[i - 1] + 1;// 由递增加 1
up[i] = up[i - 1];
} else {// 相等，状态顺位
down[i] = down[i - 1];
up[i] = up[i - 1];
}
}
return Math.max(down[nums.length - 1], up[nums.length - 1]);
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode/
// 由于状态只依赖于前一个值，进行空间优化
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2)
return nums.length;
int down = 1, up = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1])
up = down + 1;
else if (nums[i] < nums[i - 1])
down = up + 1;
}
return Math.max(down, up);
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
