o(n) time solution


  • 0
    Z
    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            if (nums.size() < 2) return nums.size();
            int res = 1;
            int flag = 0;
            int pre = nums[0];
            int change = 0;
            for (int i = 1; i < nums.size(); ++i) {
                if (nums[i] == pre) continue;
                if (nums[i] > pre) {
                    if (flag == 0) {
                        change = 1;
                        ++res;
                    }
                    else if (flag == 1) {
                        change = 0;
                    }
                    else {
                        change = 1;
                        ++res;
                    }
                }
                else if (nums[i] < pre) {
                    if (flag == 0) {
                        change = -1;
                        ++res;
                    }
                    else if (flag == -1) {
                        change = 0;
                    }
                    else {
                        change = -1;
                        ++res;
                    }
                }
                if (change == 1) flag = 1; //if flag is 1, we need small one
                else if(change == -1) flag = -1;
                pre = nums[i];
            }
            return res;
        }
    };

Log in to reply
 

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