关键字: "贪心"、"动态规划"、"具体分析"
题目描述
在一个数组中选出相对大小交替的最长子序列。
LeetCode-376-mid-摆动序列
分析
- 摆动序列：对于非边界点，是峰顶
或谷底
。
- 最长摆动序列个数有很多，但是最长摆动序列的长度受限。
- 生成式地考虑：对于一个已有的摆动序列，在不知道数组中下一个值arr[i+1]的情况下，如果此摆动序列目前为末尾上升序列，则其最后一个值越大，将arr[i+1]附加在该上升摆动序列末尾形成新的下降摆动序列的概率就越大。
（与动态规划解这道题相比）总的来说，本题的最佳解题方式为贪心：计数拐点个数即可。
解题思路（贪心）
对于摆动序列，每次末尾值的选择，如果当前是上升摆动序列，且下一个值arr[i+1]比摆动序列最后一个值还要大，则将摆动序列的末尾值更新为arr[i+1]，结果仍然保持为上升摆动序列且长度不增加。如果下一个值更小，则长度增加，转变为下降摆动序列。
即为在寻找序列的峰值和谷底数目。
算法
INPUT: nums[]
OUTPUT: maxLen
if nums.size() < 1 :
return nums.size()
arr <- nums 去重
isUp = (nums[1]>nums[0])
count = 1
for i = 2 to arr.size():
if (nums[i]>nums[i-1]) ^ isUp :
isUp = !isUp
count += 1
maxLen = count + 1
return maxLen
数据结构
不需要特殊的读写等功能，线性表遍历即可。
复杂度分析
时间复杂度：去重(O(n))+遍历球峰顶与谷底数目(O(n)) = O(n)
空间复杂度：O(n)
代码实现
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
//[0,0] 输出为1； 去除相邻重复
if ( nums.size() < 1 )
return 0 ;
vector<int> arr ;
arr.push_back( nums[0] ) ;
for ( int i = 1 ; i < nums.size() ; ++ i ){
if ( nums[i] == nums[i-1] ){
continue ;
}
arr.push_back(nums[i]) ;
}
//count 为摆动次数
if ( arr.size() < 2 ){
return arr.size() ;
}
bool flag = (arr[1] > arr[0]) ;
int count = 1;
for ( int i = 2 ; i < arr.size() ; ++i ){
if ( (arr[i] > arr[i-1]) ^ flag ){
flag = !flag ;
++ count ;
}
}
return count+1 ;
}
};
解题思路（动态规划1）
up[i] 记录以i结尾的最长上升摆动序列
down[i] 记录以i结尾的最长下降摆动序列
对于k+1:
以k+1结尾的最长上升摆动序列：满足j < k+1且nums[j] < nums[k+1]的down[j] 的最大值+1产生
以k+1结尾的最长下降摆动序列：满足j < k+1且nums[j] > nums[k+1]的up[j] 的最大值+1产生
迭代公式:
迭代公式:
算法
INPUT: nums[]
OUTPUT: maxLen
if nums.size() < 1 :
return nums.size()
arr <- nums 去重
up, down <- [1]
for i = 1 to arr.size() :
for j = 0 to i-1 :
if ( nums[i] > nums[j] )
up[i] = max( up[i], down[j]+1 )
if ( nums[i] < nums[j] )
down[i] = max( down[i], up[j]+1 )
数据结构
不需要特殊的读写等功能，vector数组存储down[]和up[]即可。
复杂度分析
时间复杂度：去重()+遍历迭代(
)=
空间复杂度：O(n)
解题思路（动态规划2）
up[i] 记录前i个数中的最长上升摆动序列
down[i] 记录前i个数中的最长下降摆动序列
对于k+1:
前k+1个数中的最长上升摆动序列：若nums[k] < nums[k+1]，则up[k+1]=max(up[k],down[k]+1); 否则 up[k+1] = up[k]
前k+1数中的最长下降摆动序列：若nums[k] > nums[k+1]，则down[k+1]=max(down[k],up[k]+1); 否则 down[k+1] = down[k]
迭代公式:
算法
INPUT: nums[]
OUTPUT: maxLen
if nums.size() < 1 :
return nums.size()
arr <- nums 去重
up, down <- [1]
for i = 1 to arr.size() :
if arr[i] > arr[i-1] :
up[i] = max(up[i-1], down[i-1]+1)
down[i] = down[i-1]
if arr[i] < arr[i-1] :
up[i] = up[i-1]
down[i] = max(down[i-1], up[i-1]+1)
return max( up[-1], down[-1])
数据结构
不需要特殊的读写等功能，vector数组存储down[]和up[]即可。
复杂度分析
时间复杂度：去重()+遍历迭代(
)=
空间复杂度：O(n)
相关问题
LeetCode-300-mid-求最长上升子序列,这道题是使用动态规划来求解，但是在题面上很相似。
在摆动序列这道题中，有文章指出这一道题目。但是该题的动态规划算法对应这里给出动态规划1(本文的第二个算法)。第二个版本的动态规划实际上用了贪心的部分来减少计算量。
PS.
相比较于其他已有的leetcode刷题笔记，我希望能够提供相关的解题分析和部分相关问题的链接，使得大家能获得一个较好的分析与相关问题的比较。
偶尔会进行类似题目的总结工作，有需要的读者可以对这份工作进行关注。
如果你发现有相关的错误或者表述不当不清晰的地方，请进行评论，我会尽快进行核对勘正。
