LeetCode 376. 摆动序列

比眉伴天荒 2023-07-03 08:17 109阅读 0赞

解题思路

时间复杂度并不理想，没有想到使用波峰，波谷的o(n)算法。
这个dp也还勉强可以通过。
思路就是先计算出差值，然后对差值数组进行dp即可。

代码

  1. class Solution { 
  2. public:
  3.     int wiggleMaxLength(vector<int>& nums) { 
  4.         int n=nums.size();
  5.         if(n==0) return 0;
  6.         if(n==1) return 1;
  7.         int a[n+3];
  8.         int dp[n+3];
  9.         for(int i=1;i<n;i++)
  10.         { 
  11.             a[i]=nums[i]-nums[i-1];
  12.         }
  13.         dp[0]=0;
  14.         for(int i=1;i<n;i++)
  15.         { 
  16.             if(a[i]==0) dp[i]=0;
  17.             else
  18.             { 
  19.                 dp[i]=1;
  20.             }
  21.         }
  22.         int M=-99999;
  23.         for(int i=1;i<n;i++)
  24.         { 
  25.             for(int j=1;j<i;j++)
  26.             { 
  27.                 if(a[i]*a[j]<0)
  28.                 { 
  29.                     dp[i]=max(dp[j]+1,dp[i]);
  30.                 }
  31.             }
  32.             M=max(M,dp[i]);
  33.         }
  34.         //if(M==0) return 0;
  35.         return M+1;
  36.     }
  37. };

发表评论

表情：
评论列表 （有 0 条评论，109人围观）

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

相关阅读

    相关 贪心算法-leetcode：376.摆动序列

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

    蔚落蔚落/ 0 赞/ 227 阅读

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

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

    深碍√TFBOYSˉ_深碍√TFBOYSˉ_/ 0 赞/ 141 阅读

    相关 LeetCode 376. 摆动序列

    解题思路 时间复杂度并不理想，没有想到使用波峰，波谷的o(n)算法。 这个dp也还勉强可以通过。 思路就是先计算出差值，然后对差值数组进行dp即可。 代码

    比眉伴天荒比眉伴天荒/ 0 赞/ 110 阅读