Short Java O(n) Greedy Solution


  • 3

    Greedy,just counting how many monotonic segments (I call segment from now on) are there.

    To see it, first convince yourself that if you have an array with n segments the longest wiggle subsequence cannot have length more than n.
    Then convince yourself that if there are n segments, you will always be able to construct a wiggle subsequence of length n.

    The code is both the process of counting segments and constructing the wiggle subsequence.

    All you need is the last element in the current longest wiggle and if the last segment is increasing.

    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int ans = 1, tail = nums[0];
        Boolean inc = null;
        for (int x: nums) {
            if (x == tail) continue;
            if (inc == null || inc != x > tail) {
                inc = x > tail;
                ans++;
            }
            tail = x;
        }
        return ans;
    }
    

Log in to reply
 

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