Skip to content

Latest commit

 

History

History
699 lines (558 loc) · 22.8 KB

0376.摆动序列.md

File metadata and controls

699 lines (558 loc) · 22.8 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

本周讲解了贪心理论基础，以及第一道贪心的题目：贪心算法：分发饼干，可能会给大家一种贪心算法比较简单的错觉，好了，接下来几天的题目难度要上来了，哈哈。

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

视频讲解

《代码随想录》算法视频公开课：贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路 1（贪心解法）

本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？

来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？

用示例二来举例，如图所示：

376.摆动序列

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

局部最优推出全局最优，并举不出反例，那么试试贪心！

（为方便表述，以下说的峰值都是指局部峰值）

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

在计算是否有峰值的时候，大家知道遍历的下标 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，如图：

376.摆动序列1

针对以上情形，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;
    }
};

其实本题看起来好像简单，但需要考虑的情况还是很复杂的，而且很难一次性想到位。

本题异常情况的本质，就是要考虑平坡， 平坡分两种，一个是 上下中间有平坡，一个是单调有平坡，如图：

思路 2（动态规划）

考虑用动态规划的思想来解决这个问题。

很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即 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)

其他语言版本

Java

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]);
    }
}

Python

贪心（版本一）

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)  # 返回上升和下降摆动序列的最大长度

Go

贪心

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
	}
}

Javascript

贪心

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);
};

Rust

贪心

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)
    }
}

C

贪心

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]);
}

TypeScript

贪心

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]);
}

Scala

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
  }
}