class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
}
};
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [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 <= 10000 <= nums[i] <= 1000
进阶：你能否用 O(n) 时间复杂度完成此题?
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-29 00:10:27
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
}
java 解法, 执行用时: 0 ms, 内存消耗: 38.8 MB, 提交时间: 2023-09-29 00:10:16
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int prevdiff = nums[1] - nums[0];
int ret = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
ret++;
prevdiff = diff;
}
}
return ret;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.4 MB, 提交时间: 2023-09-29 00:09:58
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
int prevdiff = nums[1] - nums[0];
int ret = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
ret++;
prevdiff = diff;
}
}
return ret;
}
};
python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-09-29 00:09:46
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return n
prevdiff = nums[1] - nums[0]
ret = (2 if prevdiff != 0 else 1)
for i in range(2, n):
diff = nums[i] - nums[i - 1]
if (diff > 0 and prevdiff <= 0) or (diff < 0 and prevdiff >= 0):
ret += 1
prevdiff = diff
return ret
javascript 解法, 执行用时: 68 ms, 内存消耗: 40.6 MB, 提交时间: 2023-09-29 00:09:31
/**
* @param {number[]} nums
* @return {number}
*/
// 贪心
var wiggleMaxLength = function(nums) {
const n = nums.length;
if (n < 2) {
return n;
}
let prevdiff = nums[1] - nums[0];
let ret = prevdiff !== 0 ? 2 : 1;
for (let i = 2; i < n; i++) {
const diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
ret++;
prevdiff = diff;
}
}
return ret;
};
javascript 解法, 执行用时: 56 ms, 内存消耗: 40.7 MB, 提交时间: 2023-09-29 00:08:49
/**
* @param {number[]} nums
* @return {number}
*/
var wiggleMaxLength1 = function(nums) {
const n = nums.length;
if (n < 2) return n;
const up = new Array(n).fill(0);
const down = new Array(n).fill(0);
up[0] = down[0] = 1;
for (let i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = Math.max(up[i - 1], down[i - 1] + 1);
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[n - 1], down[n - 1]);
};
var wiggleMaxLength2 = function(nums) {
const n = nums.length;
if (n < 2) {
return n;
}
let up = down = 1;
for (let i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = Math.max(up, down + 1);
} else if (nums[i] < nums[i - 1]) {
down = Math.max(up + 1, down);
}
}
return Math.max(up, down);
};
var wiggleMaxLength = function(nums) {
const n = nums.length;
if (n < 2) {
return n;
}
let up = down = 1;
for (let i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
};
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-29 00:07:52
class Solution {
public:
int wiggleMaxLength1(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
vector<int> up(n), down(n);
up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = max(up[i - 1], down[i - 1] + 1);
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = max(up[i - 1] + 1, down[i - 1]);
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return max(up[n - 1], down[n - 1]);
}
int wiggleMaxLength2(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = max(up, down + 1);
} else if (nums[i] < nums[i - 1]) {
down = max(up + 1, down);
}
}
return max(up, down);
}
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return max(up, down);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.2 MB, 提交时间: 2023-09-28 23:59:28
class Solution {
public int wiggleMaxLength1(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int[] up = new int[n];
int[] down = new int[n];
up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = Math.max(up[i - 1], down[i - 1] + 1);
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[n - 1], down[n - 1]);
}
public int wiggleMaxLength2(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = Math.max(up, down + 1);
} else if (nums[i] < nums[i - 1]) {
down = Math.max(up + 1, down);
}
}
return Math.max(up, down);
}
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-28 23:58:37
func wiggleMaxLength1(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
up := make([]int, n)
down := make([]int, n)
up[0] = 1
down[0] = 1
for i := 1; i < n; i++ {
if nums[i] > nums[i-1] {
up[i] = max(up[i-1], down[i-1]+1)
down[i] = down[i-1]
} else if nums[i] < nums[i-1] {
up[i] = up[i-1]
down[i] = max(up[i-1]+1, down[i-1])
} else {
up[i] = up[i-1]
down[i] = down[i-1]
}
}
return max(up[n-1], down[n-1])
}
func wiggleMaxLength2(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
up, down := 1, 1
for i := 1; i < n; i++ {
if nums[i] > nums[i-1] {
up = max(up, down+1)
} else if nums[i] < nums[i-1] {
down = max(up+1, down)
}
}
return max(up, down)
}
func wiggleMaxLength(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
up, down := 1, 1
for i := 1; i < n; i++ {
if nums[i] > nums[i-1] {
up = down + 1
} else if nums[i] < nums[i-1] {
down = up + 1
}
}
return max(up, down)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-09-28 23:57:44
'''
up[i] 表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。
down[i] 表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。
'''
class Solution:
def wiggleMaxLength1(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return n
up = [1] + [0] * (n - 1)
down = [1] + [0] * (n - 1)
for i in range(1, n):
if nums[i] > nums[i - 1]:
up[i] = max(up[i - 1], down[i - 1] + 1)
down[i] = down[i - 1]
elif nums[i] < nums[i - 1]:
up[i] = up[i - 1]
down[i] = max(up[i - 1] + 1, down[i - 1])
else:
up[i] = up[i - 1]
down[i] = down[i - 1]
return max(up[n - 1], down[n - 1])
# 仅需要前一个状态来进行转移，所以我们维护两个变量即可
def wiggleMaxLength2(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return n
up = down = 1
for i in range(1, n):
if nums[i] > nums[i - 1]:
up = max(up, down + 1)
elif nums[i] < nums[i - 1]:
down = max(up + 1, down)
return max(up, down)
# 再优化
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return n
up = down = 1
for i in range(1, n):
if nums[i] > nums[i - 1]:
up = down + 1
elif nums[i] < nums[i - 1]:
down = up + 1
return max(up, down)