参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
本周讲解了贪心理论基础，以及第一道贪心的题目：贪心算法：分发饼干，可能会给大家一种贪心算法比较简单的错觉，好了，接下来几天的题目难度要上来了，哈哈。
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [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
本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？
来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？
用示例二来举例，如图所示：
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
局部最优推出全局最优，并举不出反例，那么试试贪心！
（为方便表述，以下说的峰值都是指局部峰值）
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）
这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点
在计算是否有峰值的时候，大家知道遍历的下标i ，计算prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。
这是我们思考本题的一个大题思路，但本题要考虑三种情况：
- 情况一：上下坡中有平坡
- 情况二：数组首尾两端
- 情况三：单调坡中有平坡
例如 [1,2,2,2,1]这样的数组，如图：
它的摇摆序列长度是多少呢？ 其实是长度是3，也就是我们在删除的时候 要不删除左面的三个2，要不就删除右边的三个2。
如图，可以统一规则，删除左边的三个2：
在图中，当i指向第一个2的时候，prediff > 0 && curdiff = 0 ，当 i 指向最后一个2的时候 prediff = 0 && curdiff < 0。
如果我们采用，删左面三个2的规则，那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值，因为他是把之前相同的元素都删掉留下的峰值。
所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)，为什么这里允许 prediff == 0 ，就是为了 上面我说的这种情况。
所以本题统计峰值的时候，数组最左面和最右面如果统计呢？
题目中说了，如果只有两个不同的元素，那摆动序列也是2。
例如序列[2,5]，如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。
这里我们可以写死，就是 如果只有两个元素，且元素不同，那么结果为2。
不写死的话，如果和我们的判断规则结合在一起呢？
可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？
之前我们在 讨论 情况一：相同数字连续 的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。
那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即preDiff = 0，如图：
针对以上情形，result初始为1（默认最右面有一个峰值），此时curDiff > 0 && preDiff <= 0，那么result++（计算了左面的峰值），最后得到的result就是2（峰值个数为2即摆动序列长度为2）
经过以上分析后，我们可以写出如下代码：
// 版本一
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 出现峰值
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
}
preDiff = curDiff;
}
return result;
}
};- 时间复杂度：O(n)
- 空间复杂度：O(1)
此时大家是不是发现 以上代码提交也不能通过本题？
所以此时我们要讨论情况三！
在版本一中，我们忽略了一种情况，即 如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图：
图中，我们可以看出，版本一的代码在三个地方记录峰值，但其实结果因为是2，因为 单调中的平坡 不能算峰值（即摆动）。
之所以版本一会出问题，是因为我们实时更新了 prediff。
那么我们应该什么时候更新prediff呢？
我们只需要在 这个坡度 摆动变化的时候，更新prediff就行，这样prediff在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。
所以本题的最终代码为：
// 版本二
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 出现峰值
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff
}
}
return result;
}
};其实本题看起来好像简单，但需要考虑的情况还是很复杂的，而且很难一次性想到位。
本题异常情况的本质，就是要考虑平坡， 平坡分两种，一个是 上下中间有平坡，一个是单调有平坡，如图：
考虑用动态规划的思想来解决这个问题。
很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i] < nums[i - 1]）。
- 设dp状态
dp[i][0]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度 - 设dp状态
dp[i][1]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
则转移方程为：
dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将nums[i]接到前面某个山谷后面，作为山峰。dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将nums[i]接到前面某个山峰后面，作为山谷。
初始状态：
由于一个数可以接到前面的某个数后面，也可以以自身为子序列的起点，所以初始状态为：dp[0][0] = dp[0][1] = 1。
C++代码如下：
class Solution {
public:
int dp[1005][2];
int wiggleMaxLength(vector<int>& nums) {
memset(dp, 0, sizeof dp);
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.size(); ++i) {
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
}
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
}
}
return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
}
};- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
进阶
可以用两棵线段树来维护区间的最大值
- 每次更新
dp[i][0]，则在tree1的nums[i]位置值更新为dp[i][0] - 每次更新
dp[i][1]，则在tree2的nums[i]位置值更新为dp[i][1] - 则dp转移方程中就没有必要j从0遍历到i-1，可以直接在线段树中查询指定区间的值即可。
时间复杂度：O(nlog n)
空间复杂度：O(n)
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
//当前差值
int curDiff = 0;
//上一个差值
int preDiff = 0;
int count = 1;
for (int i = 1; i < nums.length; i++) {
//得到当前差值
curDiff = nums[i] - nums[i - 1];
//如果当前差值和上一个差值为一正一负
//等于0的情况表示初始时的preDiff
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
count++;
preDiff = curDiff;
}
}
return count;
}
}// DP
class Solution {
public int wiggleMaxLength(int[] nums) {
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[][] = new int[nums.length][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.length; i++){
//i 自己可以成为波峰或者波谷
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; j++){
if (nums[j] > nums[i]){
// i 是波谷
dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
if (nums[j] < nums[i]){
// i 是波峰
dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
}
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}贪心
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
preC,curC,res = 0,0,1 #题目里nums长度大于等于1，当长度为1时，其实到不了for循环里去，所以不用考虑nums长度
for i in range(len(nums) - 1):
curC = nums[i + 1] - nums[i]
if curC * preC <= 0 and curC !=0: #差值为0时，不算摆动
res += 1
preC = curC #如果当前差值和上一个差值为一正一负时，才需要用当前差值替代上一个差值
return res动态规划
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
# 0 i 作为波峰的最大长度
# 1 i 作为波谷的最大长度
# dp是一个列表，列表中每个元素是长度为 2 的列表
dp = []
for i in range(len(nums)):
# 初始为[1, 1]
dp.append([1, 1])
for j in range(i):
# nums[i] 为波谷
if nums[j] > nums[i]:
dp[i][1] = max(dp[i][1], dp[j][0] + 1)
# nums[i] 为波峰
if nums[j] < nums[i]:
dp[i][0] = max(dp[i][0], dp[j][1] + 1)
return max(dp[-1][0], dp[-1][1])class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
# up i作为波峰最长的序列长度
# down i作为波谷最长的序列长度
n = len(nums)
# 长度为0和1的直接返回长度
if n<2: return n
for i in range(1,n):
if nums[i]>nums[i-1]:
# nums[i] 为波峰，1. 前面是波峰，up值不变，2. 前面是波谷，down值加1
# 目前up值取两者的较大值(其实down+1即可，可以推理前一步down和up最多相差1，所以down+1>=up)
up = max(up, down+1)
elif nums[i]<nums[i-1]:
# nums[i] 为波谷，1. 前面是波峰，up+1，2. 前面是波谷，down不变，取较大值
down = max(down, up+1)
return max(up, down)贪心
func wiggleMaxLength(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
ans := 1
prevDiff := nums[1] - nums[0]
if prevDiff != 0 {
ans = 2
}
for i := 2; i < n; i++ {
diff := nums[i] - nums[i-1]
if diff > 0 && prevDiff <= 0 || diff < 0 && prevDiff >= 0 {
ans++
prevDiff = diff
}
}
return ans
}动态规划
func wiggleMaxLength(nums []int) int {
n := len(nums)
if n <= 1 {
return n
}
dp := make([][2]int, n)
// i 0 作为波峰的最大长度
// i 1 作为波谷的最大长度
dp[0][0] = 1
dp[0][1] = 1
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] > nums[i] { //nums[i]为波谷
dp[i][1] = max(dp[i][1], dp[j][0]+1)
}
if nums[j] < nums[i] { //nums[i]为波峰 或者相等
dp[i][0] = max(dp[i][0], dp[j][1]+1)
}
if nums[j] == nums[i] { //添加一种情况，nums[i]为相等
dp[i][0] = max(dp[i][0], dp[j][0]) //波峰
dp[i][1] = max(dp[i][1], dp[j][1]) //波谷
}
}
}
return max(dp[n-1][0], dp[n-1][1])
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}贪心
var wiggleMaxLength = function(nums) {
if(nums.length <= 1) return nums.length
let result = 1
let preDiff = 0
let curDiff = 0
for(let i = 0; i < nums.length - 1; i++) {
curDiff = nums[i + 1] - nums[i]
if((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
result++
preDiff = curDiff
}
}
return result
};动态规划
var wiggleMaxLength = function(nums) {
if (nums.length === 1) return 1;
// 考虑前i个数，当第i个值作为峰谷时的情况（则第i-1是峰顶）
let down = 1;
// 考虑前i个数，当第i个值作为峰顶时的情况（则第i-1是峰谷）
let up = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
down = Math.max(up + 1, down);
}
if (nums[i] > nums[i - 1]) {
up = Math.max(down + 1, up)
}
}
return Math.max(down, up);
};贪心
impl Solution {
pub fn wiggle_max_length(nums: Vec<i32>) -> i32 {
let len = nums.len() as usize;
if len <= 1 {
return len as i32;
}
let mut preDiff = 0;
let mut curDiff = 0;
let mut result = 1;
for i in 0..len-1 {
curDiff = nums[i+1] - nums[i];
if (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0) {
result += 1;
preDiff = curDiff;
}
}
result
}
}贪心
int wiggleMaxLength(int* nums, int numsSize){
if(numsSize <= 1)
return numsSize;
int length = 1;
int preDiff , curDiff;
preDiff = curDiff = 0;
for(int i = 0; i < numsSize - 1; ++i) {
// 计算当前i元素与i+1元素差值
curDiff = nums[i+1] - nums[i];
// 若preDiff与curDiff符号不符，则子序列长度+1。更新preDiff的符号
// 若preDiff与curDiff符号一致，当前i元素为连续升序/连续降序子序列的中间元素。不被记录入长度
// 注：当preDiff为0时，curDiff为正或为负都属于符号不同
if((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
preDiff = curDiff;
length++;
}
}
return length;
}动态规划
int max(int left, int right)
{
return left > right ? left : right;
}
int wiggleMaxLength(int* nums, int numsSize){
if(numsSize <= 1)
{
return numsSize;
}
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[numsSize][2];
for(int i = 0; i < numsSize; i++)
{
dp[i][0] = 1;
dp[i][1] = 1;
for(int j = 0; j < i; j++)
{
// nums[i] 为山谷
if(nums[j] > nums[i])
{
dp[i][1] = max(dp[i][1], dp[j][0] + 1);
}
// nums[i] 为山峰
if(nums[j] < nums[i])
{
dp[i][0] = max(dp[i][0], dp[j][1] + 1);
}
}
}
return max(dp[numsSize - 1][0], dp[numsSize - 1][1]);
}贪心
function wiggleMaxLength(nums: number[]): number {
let length: number = nums.length;
if (length <= 1) return length;
let preDiff: number = 0;
let curDiff: number = 0;
let count: number = 1;
for (let i = 1; i < length; i++) {
curDiff = nums[i] - nums[i - 1];
if (
(preDiff <= 0 && curDiff > 0) ||
(preDiff >= 0 && curDiff < 0)
) {
preDiff = curDiff;
count++;
}
}
return count;
};动态规划
function wiggleMaxLength(nums: number[]): number {
const length: number = nums.length;
if (length <= 1) return length;
const dp: number[][] = new Array(length).fill(0).map(_ => []);
dp[0][0] = 1; // 第一个数作为波峰
dp[0][1] = 1; // 第一个数作为波谷
for (let i = 1; i < length; i++) {
dp[i][0] = 1;
dp[i][1] = 1;
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
for (let j = 0; j < i; j++) {
if (nums[j] > nums[i]) dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
}
return Math.max(dp[length - 1][0], dp[length - 1][1]);
};object Solution {
def wiggleMaxLength(nums: Array[Int]): Int = {
if (nums.length <= 1) return nums.length
var result = 1
var curDiff = 0 // 当前一对的差值
var preDiff = 0 // 前一对的差值
for (i <- 1 until nums.length) {
curDiff = nums(i) - nums(i - 1) // 计算当前这一对的差值
// 当 curDiff > 0 的情况，preDiff <= 0
// 当 curDiff < 0 的情况，preDiff >= 0
// 这两种情况算是两个峰值
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
result += 1 // 结果集加 1
preDiff = curDiff // 当前差值赋值给上一轮
}
}
result
}
}
