Java O(n) greedy solution


  • 7
    Q
    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if(nums.length <= 1) return nums.length;
            int count = 1;
            Boolean prevInc = null;
            for(int i = 1; i < nums.length; i++) {
                if(nums[i] > nums[i - 1] && (prevInc == null || !prevInc)) {
                    prevInc = true;
                    count++;
                } else if(nums[i] < nums[i - 1] && (prevInc == null || prevInc)) {
                    prevInc = false;
                    count++;
                }
            }
            return count;
        }
    }

  • 0

    Do you really need max? I think you can just return count.


  • 0
    Q

    @StefanPochmann You are right, will update it, thanks.


  • 0
    Q

    Re: Java O(n) greedy solution

    Can you explain why this works?

    I tried your solution on this [1,17,5,10,13,15,10,5,16,8] and it returned:
    1 17 5 10 10 16 18


  • 0
    Q

    @quincyhehe
    for [1, 17, 5, 10, 13, 15, 10, 5, 16, 8],
    my solution should return:[1, 17, 5, 15, 5, 16, 8].
    To better explain the idea, let's name the result array as int[] res .
    Suppose you've already got res[j - 1] > res[j - 2], which means prevInc == true, now you need a decreasing number to get the longest subsequence. If you get an increasing number now, you need to update res[j - 1] with num[i]. Because the bigger your res[j - 1] is, the easier you can find a res[j] < res[j - 1] .


  • 0
    Q

    @qianzhige

    Thank you very much for your reply.

    I tried this

    public static int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) return nums.length;
        int count = 1;
        Boolean prevInc = null;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] > nums[i - 1] && (prevInc == null || !prevInc)) {
            	System.out.println(nums[i]);
                prevInc = true;
                count++;
            } else if(nums[i] < nums[i - 1] && (prevInc == null || prevInc)) {
            	System.out.println(nums[i]);
                prevInc = false;
                count++;
            }
        }
        return count;
    }
    

    and the printed number is:
    17 5 10 10 16 8

    I'm very confused.


  • 1

    @quincyhehe To get the exact wiggle subsequence, you should always pick the local maximum/minimum. But what you print out is the element next to the local maximum/minimum, so this may be confusing. You should print nums[i-1] (you may also need to print nums[i] as the last element, if you reach the end of the input sequence).


  • 0
    M

    @qianzhige said in Java O(n) greedy solution:

    Boolean prevInc

    The way to use boolean flag is fantastic !


  • 0
    M

    I used DP to get an O(n^2) solution because I could not convinced myself that greedy solution will work. Why short-sightedness of greedy algorithm will not apply to this problem? Do you have a general idea about when to be greedy?


Log in to reply
 

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