辽宁网站建站系统平台,常宁市城市建设规划管理局网站,湘潭网站建设优化建站,在百度怎么建立自己的网站题意理解#xff1a; 如果连续数字之间的差严格地在正数和负数之间交替#xff0c;则数字序列称为 摆动序列 如果是摆动序列#xff0c;前后差值呈正负交替出现 为保证摆动序列尽可能的长#xff0c;我们可以尽可能的保留峰值#xff0c;#xff0c;删除上下坡的中间值 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 如果是摆动序列前后差值呈正负交替出现 为保证摆动序列尽可能的长我们可以尽可能的保留峰值删除上下坡的中间值或平坡值。 解题思路 已知要删除一些值来保证摆动序列的话应该保留峰值删除上下坡、平坡的值。 并且摆动序列两数差值正负交替出现。 所以我们需要一个值preDiff来记录前一个数和当前数的差值。 还需要一个指向当前值和后一个值得指针来计算两数差值看两者是否正负交替出现。 1.贪心解题 为实现该算法解题我们需要定义cur和after得指针来记录当前差值 需要定义preDiff来记录前一个差值判断当前值是否是峰值保留峰值删除坡值。 这里的删除并不是真正的删除指示不记录此处的result result来记录正负值变化次数n指示序列应为n1 public int wiggleMaxLength(int[] nums) {int result0;int preDiff0;for(int i0;inums.length-1;i){if((preDiff0nums[i1]-nums[i]0)||(preDiff0nums[i1]-nums[i]0)){result;//只记录有正负性的preDiffpreDiffnums[i1]-nums[i];}}//result记录了中间值正负变化的次数n指示n1个数的序列有n个中间值return result1;}
2.分析 时间复杂度O(n) 空间复杂度O(n)
