Easy greedy solution C++(0ms)


  • 0
    B

    There are three situations when we traverse the array, that is increasing, decreasing and equal. What we really care about is how many times the traversing progress switch between increasing and decreasing.
    The reason we can use greedy here is that when we meet a consecutive increasing or decreasing block we can just record the maximum or minimum value in that block. Because if the max or min will not form next wiggle, any number before them is not able to do that either.

    Here is the code:

    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            int size = nums.size();
            if(size == 0) return 0;
            int res = 1;                            //result
            int up = 0;
            for(int i = 1; i < size; i++){
                if(nums[i] < nums[i-1]){
                    if(up == 0 || up == -1){  //first two value or a wiggle
                        res++;
                        up = 1;
                    }
                }
                else if(nums[i] > nums[i-1]){
                    if(up == 0 || up == 1){
                        res++;
                        up = -1;
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.