0376.摆动序列
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
# 376. 摆动序列 [力扣题目链接](https://leetcode.cn/problems/wiggle-subsequence/) 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [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 ## 算法公开课 **[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列](https://www.bilibili.com/video/BV17M411b7NS)，相信结合视频在看本篇题解，更有助于大家对本题的理解**。 ## 思路 ### 思路 1（贪心解法） 本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。 相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？ 来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？ 用示例二来举例，如图所示：  **局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值**。 **整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列**。 局部最优推出全局最优，并举不出反例，那么试试贪心！ （为方便表述，以下说的峰值都是指局部峰值） **实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）** **这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点** 在计算是否有峰值的时候，大家知道遍历的下标 i ，计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果`prediff < 0 && curdiff > 0` 或者 `prediff > 0 && curdiff < 0` 此时就有波动就需要统计。 这是我们思考本题的一个大题思路，但本题要考虑三种情况： 1. 情况一：上下坡中有平坡 2. 情况二：数组首尾两端 3. 情况三：单调坡中有平坡 #### 情况一：上下坡中有平坡 例如 [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;
}
};
// 版本二
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;
}
};
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]);
}
};
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):
if len(nums) <= 1:
return len(nums) # 如果数组长度为0或1，则返回数组长度
curDiff = 0 # 当前一对元素的差值
preDiff = 0 # 前一对元素的差值
result = 1 # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）
for i in range(len(nums) - 1):
curDiff = nums[i + 1] - nums[i] # 计算下一个元素与当前元素的差值
# 如果遇到一个峰值
if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
result += 1 # 峰值个数加1
preDiff = curDiff # 注意这里，只在摆动变化的时候更新preDiff
return result # 返回最长摆动子序列的长度
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums) # 如果数组长度为0或1，则返回数组长度
preDiff,curDiff ,result = 0,0,1 #题目里nums长度大于等于1，当长度为1时，其实到不了for循环里去，所以不用考虑nums长度
for i in range(len(nums) - 1):
curDiff = nums[i + 1] - nums[i]
if curDiff * preDiff <= 0 and curDiff !=0: #差值为0时，不算摆动
result += 1
preDiff = curDiff #如果当前差值和上一个差值为一正一负时，才需要用当前差值替代上一个差值
return result
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):
dp = [[0, 0] for _ in range(len(nums))] # 创建二维dp数组，用于记录摆动序列的最大长度
dp[0][0] = dp[0][1] = 1 # 初始条件，序列中的第一个元素默认为峰值，最小长度为1
for i in range(1, len(nums)):
dp[i][0] = dp[i][1] = 1 # 初始化当前位置的dp值为1
for j in range(i):
if nums[j] > nums[i]:
dp[i][1] = max(dp[i][1], dp[j][0] + 1) # 如果前一个数比当前数大，可以形成一个上升峰值，更新dp[i][1]
for j in range(i):
if nums[j] < nums[i]:
dp[i][0] = max(dp[i][0], dp[j][1] + 1) # 如果前一个数比当前数小，可以形成一个下降峰值，更新dp[i][0]
return max(dp[-1][0], dp[-1][1]) # 返回最大的摆动序列长度
class Solution:
def wiggleMaxLength(self, nums):
if len(nums) <= 1:
return len(nums) # 如果数组长度为0或1，则返回数组长度
up = down = 1 # 记录上升和下降摆动序列的最大长度
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
up = down + 1 # 如果当前数比前一个数大，则可以形成一个上升峰值
elif nums[i] < nums[i-1]:
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 {
if nums.len() == 1 {
return 1;
}
let mut res = 1;
let mut pre_diff = 0;
for i in 0..nums.len() - 1 {
let cur_diff = nums[i + 1] - nums[i];
if (pre_diff <= 0 && cur_diff > 0) || (pre_diff >= 0 && cur_diff < 0) {
res += 1;
pre_diff = cur_diff;
}
}
res
}
}
impl Solution {
pub fn wiggle_max_length(nums: Vec<i32>) -> i32 {
if nums.len() == 1 {
return 1;
}
let (mut down, mut up) = (1, 1);
for i in 1..nums.len() {
// i - 1 为峰顶
if nums[i] < nums[i - 1] {
down = down.max(up + 1);
}
// i - 1 为峰谷
if nums[i] > nums[i - 1] {
up = up.max(down + 1);
}
}
down.max(up)
}
}
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
}
}
