376. Wiggle Subsequence（贪心）

1.题目描述

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Input: [1,7,4,9,2,5]
Output: 6
           

The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
           

There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2
           

2.代码

思想：读懂题意很重要！

题目的大概意思是说，从原序列中删除某些元素得到这样的子序列：前后差值正负摆动。

贪心：

1. 当出现连续的“正”值时，如：1 2 3 4 5 6 5 4 3 4 5，取这个递增的子序列1 2 3 4 5 6的最后一个元素6加入；

2. 同样的，当出现连续的“负值”时，取子序列 5 4 3 中的3加入

如此便达到贪心的目的：因此取差值为正的最大的元素加入时，我们期望下一个差值是负，而且给这样一个值的到来争取到了足够的差值范围（只要和前年的最大值凑成差为负值），类似的，对于取差值为负的最小元素加入，原理是一样的。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= ) return nums.size();
        vector<int> q;
        int res = ;
        bool lastDiff, currentDiff;
        for(int i = ; i< nums.size();++i) {
            int num = nums[i];
            if(q.empty()) {
                q.push_back(num);
                res++;
            } else if(q.size() == ) {
                int back = q[q.size()-];
                if(num - back > ) lastDiff = true;
                else if(num - back == ) continue; 
                else lastDiff = false;
                q.push_back(num);
                res++;  
            } else {
                int end = q.size()-;
                int t = q[end];
                if(num - t > ) currentDiff = true;
                else if(num - t == ) continue; 
                else currentDiff = false;

                if(currentDiff != lastDiff) {
                    q.push_back(num);
                    res++;
                    lastDiff = currentDiff;
                } else {
                    q.erase(q.end()-);
                    q.push_back(num);       
                }   
            }   
        }
        return res;
    }
};