It is just finding maxima/minima of a sequence O(N)/O(1) time/space.


  • 0
    S

    Please correct me if wrong! The idea is of course greedy. When picking the wiggle subsequence, for example sequence is [1, 17, 5, 10, 14, 15, 10, 5], when sequence is increasing, i.e. 5, 10, 14, 15, picking the bigger one in the subsequence is always better, same for decreasing part. So just pick all maxima/minima of the sequence. And remember first and last element can always be included.

    public int wiggleMaxLength(int[] nums) {
            int len = nums.length;
            int rst = 0;
            int prv = -1;
            int cur = 0;
            int nxt = cur;
            while (cur < len) {
                while (cur < len && nxt < len && nums[nxt] == nums[cur]) {
                    nxt++; // To handle the case that duplicate num at maxima/minima point.
                }
                if (prv < 0 || nxt >= len) {
                    rst++; // Include first and last element.
                } else if (nums[prv] < nums[cur] && nums[cur] > nums[nxt]) {
                    rst++; // Maxima.
                } else if (nums[prv] > nums[cur] && nums[cur] < nums[nxt]) {
                    rst++; // Minima.
                }
                // Move ptrs.
                prv = cur;
                cur = nxt;
                                                 
            }
            return rst;
        }
    

Log in to reply
 

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