数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中的摆动子序列
假设我们有一系列数字，如果连续数字之间的差严格地在正数和负数之间交替，则称之为摆动序列。第一个差可以是正数或负数。少于两个元素的序列微不足道地是一个摆动序列。例如，[1,7,4,9,2,5] 是一个摆动序列，因为如果看到，差值 (6,-3,5,-7,3) 是交替的正数和负数。但是，[1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个是因为它的前两个差是正数，第二个是因为它的最后一个差是零。
所以我们有一系列整数，我们必须找到最长子序列的长度，该子序列是一个摆动序列。子序列是通过从原始序列中删除一些数字（最终也为零）获得的，并将剩余的数字按其原始顺序保留。因此，如果输入类似于 [1,7,4,9,2,5]，则输出将为 6，因为整个序列是一个摆动序列。
为了解决这个问题，我们将遵循以下步骤：
n := nums 的大小
如果 n 为 0，则返回 0
设置 up := 1 和 down := 1
对于 i 从 1 到 n – 1 的范围
如果 nums[i] > nums[i – 1]，则 up := down + 1
否则，当 nums[i] < nums[i – 1] 时，则 down := up + 1
返回 up 和 down 的最大值
示例 (C++)
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(!n) return 0;
int up = 1;
int 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);
}
};
main(){
Solution ob;
vector<int> v = {1,7,4,9,2,5};
cout << (ob.wiggleMaxLength(v));
}输入
[1,7,4,9,2,5]
输出
6
更新于：2020年5月2日
248 次查看
广告