376. 摆动序列

🟠 🔖 贪心 数组 动态规划 🔗 力扣open in new window LeetCodeopen in new window

题目

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return _the length of the longestwiggle subsequence of _nums.

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

Example 2:

Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length.
One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

题目大意

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。 第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

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

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入： nums = [1,7,4,9,2,5]
输出： 6
解释： 整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入： nums = [1,17,5,10,13,15,10,5,16,8]
输出： 7
解释： 这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入： nums = [1,2,3,4,5,6,7,8,9]
输出： 2

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

进阶： 你能否用 O(n) 时间复杂度完成此题?

解题思路

动态规划思路
- 维护两个状态变量 increase 和 decrease：
  - increase: 以当前元素为结尾的 最近一次上升摆动序列的长度。
  - decrease: 以当前元素为结尾的 最近一次下降摆动序列的长度。
状态转移 遍历数组时，根据当前元素与前一个元素的大小关系更新状态：
- 如果 nums[i] > nums[i - 1]
  当前元素为上升趋势，需延续或更新上升摆动序列： increase = decrease + 1 解释：当前元素可以接在之前的下降序列后，因此长度增加。
- 如果 nums[i] < nums[i - 1]
  当前元素为下降趋势，需延续或更新下降摆动序列： decrease = increase + 1 解释：当前元素可以接在之前的上升序列后，因此长度增加。
- 如果 nums[i] === nums[i - 1]
  跳过，序列不变。
结果计算
- 遍历结束后，返回 Math.max(increase, decrease) 即为最终结果。

复杂度分析

时间复杂度：O(n)，仅需一次遍历即可完成状态更新。
空间复杂度：O(1)，仅使用常数空间变量。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function (nums) {
	if (nums.length < 2) return nums.length;
	let increase = 1,
		decrease = 1;
	for (let i = 1; i < nums.length; i++) {
		if (nums[i] > nums[i - 1]) {
			increase = decrease + 1;
		} else if (nums[i] < nums[i - 1]) {
			decrease = increase + 1;
		}
	}
	return Math.max(increase, decrease);
};

376. 摆动序列

# 376. 摆动序列

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

376. 摆动序列

题目

题目大意

解题思路

复杂度分析

代码

相关题目