LeetCode 376. Wiggle Subsequence (贪心)

Bertha 。 2023-05-30 10:46 49阅读 0赞

题目意思:

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

给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,返回子序列的长度

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1

贪心思路:

将两两之间的差值算出来存起来,遍历差值,符合条件入栈,不符合往下找知道符合的数入栈,最终返回栈的长度+1
注意边界判断,比如空数组

代码:

  1. class Solution {
  2. public:
  3. int wiggleMaxLength(vector<int>& nums) {
  4. vector<int > tmp;
  5. stack<int > s;
  6. //贪心思路:将两两之间的差值算出来存起来,遍历差值,符合条件入栈,不符合往下找知道符合的数入栈,最终返回栈的长度+1
  7. //注意边界判断,比如空数组
  8. for(int i = 1; i < nums.size(); i++){
  9. tmp.push_back(nums[i] - nums[i-1]);
  10. }
  11. if(tmp.size()){
  12. //两个数差值为0不可
  13. if(tmp[0] != 0) s.push(tmp[0]);
  14. }
  15. for(int i = 1; i < tmp.size(); i++){
  16. //避免差值都是零导致空栈越界情况
  17. if(tmp[i] != 0 && !s.size()){
  18. s.push(tmp[i]);
  19. }else if(tmp[i] != 0 && s.top() * tmp[i] < 0){ //互异
  20. s.push(tmp[i]);
  21. }
  22. }
  23. //判断空数组情况
  24. if(s.size() == 0){
  25. if(nums.size() == 0) return 0;
  26. else return 1;
  27. }else return s.size() + 1;
  28. }
  29. };

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2

发表评论

表情:
评论列表 (有 0 条评论,49人围观)

还没有评论,来说两句吧...

相关阅读

    相关 贪心算法-leetcode376.摆动序列

    问题描述 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, \

    相关 贪心——376. 摆动序列

    1 题目描述 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也