美文网首页
376. 摆动序列

376. 摆动序列

作者: 梦想黑客 | 来源:发表于2020-03-08 15:57 被阅读0次

    题目描述

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

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

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

    示例 1:

    输入: [1,7,4,9,2,5]
    输出: 6 
    解释: 整个序列均为摆动序列。
    

    示例 2:

    输入: [1,17,5,10,13,15,10,5,16,8]
    输出: 7
    解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。
    

    示例 3:

    输入: [1,2,3,4,5,6,7,8,9]
    输出: 2
    

    进阶:
    你能否用 O(n) 时间复杂度完成此题?

    解法

    class Solution {
    
        //时间复杂度O(n),空间复杂度O(1)
        //解法:贪心思想是序列上升或者下降的时候,取最大(上升)或者最小(下降)的,保证后面一位尽可能满足摇摆
    
        private static final int STATE_START = 0;
        private static final int STATE_UP = 1;
        private static final int STATE_DOWN = 2;
    
        public int wiggleMaxLength(int[] nums) {
            if(nums.length <= 1) return nums.length;
    
            int state = STATE_START;
            int count = 1;
            for(int i=1; i<nums.length; i++){
    
                switch(state){
                    case STATE_START:
                        //开始状态,除了相等,会转换成上升或者下降状态
                        if(nums[i] > nums[i-1]){
                            state = STATE_UP;
                            count++;
                        }else if(nums[i] < nums[i-1]){
                            state = STATE_DOWN;
                            count++;
                        }
                        break;
                    case STATE_UP:
                        //上升状态,只能转换成下降状态
                        if(nums[i] < nums[i-1]){
                            state = STATE_DOWN;
                            count++;
                        }
                        break; 
                    case STATE_DOWN:
                        //下降状态,只能转换成上升状态
                        if(nums[i] > nums[i-1]){
                            state = STATE_UP;
                            count++;
                        }
    
                        break;
                }    
            }
            return count;
        }
    }
    

    相关文章

      网友评论

          本文标题:376. 摆动序列

          本文链接:https://www.haomeiwen.com/subject/fnkklhtx.html