贪心
解题思路
刷了好几道贪心的题，还是对贪心比较模糊，这道题我是真想不到，为什么要用贪心，坚持写题解；
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值；
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列；
实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度），这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点；
本题的一个大体思路，要考虑两种情况：
- 情况一：相同数字连续；
- 情况二：单调坡度有平坡；
复杂度
-
时间复杂度：
O(n)，其中 n 是序列的长度； -
空间复杂度：
O(1)；
代码实现
var wiggleMaxLength = function (nums) {
const n = nums.length;
if (n < 2) return n;
let prevdiff = nums[1] - nums[0]; // 记录之前的坡度（当前是初始坡度）
let res = prevdiff !== 0 ? 2 : 1; // 判断前两个节点是否全部满足摆动序列
// 在 [第二个元素，最后一个元素] 这个区间计算摆动
for (let i = 2; i < n; i++) {
// 当前坡度
const currdiff = nums[i] - nums[i - 1];
// 出现峰值
if ((currdiff > 0 && prevdiff <= 0) || (currdiff < 0 && prevdiff >= 0)) {
res++;
prevdiff = currdiff; // 更新峰值
}
}
return res;
};
动态规划
解题思路
先欠着😢
复杂度
代码实现
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 455. 分发饼干
上一篇
评论
