【算法与数据结构】376、LeetCode摆动序列
2023-12-15 10:51:04
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
??思路分析:本题难点在于要考虑到不同序列的情况,具体来说要考虑一下几种特殊情况:
- 1、上下坡中有平坡:[1 2 2 2 1];
- 2、数组首尾两端:[1 2] [1 1 2];
- 3、单调坡中有平坡: [1 2 2 2 3 4 5];
??观察一下不难发现,序列的最大摆动子序列的长度和局部峰值有关系。因此我们首先要找的就是局部峰值。定义preDiff和curDiff分别记录上一个差值和当前差值。对于小于等于1的序列直接输出其长度。贪心算法要做的就是删除单调区间内的元素。事实上也不需要去修改原序列,只需删除单一坡度上的节点,然后统计长度考虑局部峰值即可。情况一种仅有最大摆动子序列长度为3,我们统一删除前两个2 变成[1 2 1]长度为3。
??对于情况2,我们假设默认最右边有一个峰值result=1,同时preDiff初始化为0,也就是说,[1 2]的序列可以看成[1 1 2]。这两个序列的最大摆动子序列长度相同,为2。
??对于情况3,我们选择在摆动变化的时候更新preDiff,而非每次curDiff变换就修改preDiff,因此在每个单调区间内preDiff只会发生一次变化。
??程序如下:
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size(); // 序列元素小于等于1的情况
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 ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) { // 出现局部峰值
result++;
preDiff = curDiff; // 只在摆动变化的时候更新preDiff
}
}
return result;
}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( 1 ) O(1) O(1)。
三、完整代码
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size(); // 序列元素小于等于1的情况
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 ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) { // 出现局部峰值
result++;
preDiff = curDiff; // 只在摆动变化的时候更新preDiff
}
}
return result;
}
};
int main() {
vector<int> nums = { 1, 17, 10, 13, 10, 16, 8 };
Solution s1;
int result = s1.wiggleMaxLength(nums);
cout << result << endl;
system("pause");
return 0;
}
end
文章来源:https://blog.csdn.net/qq_45765437/article/details/135008748
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!