Java 1 ms 20-line O(n) solution. Clean code easy to understand with detailed explanation


  • 0

    Key points:

    1. This problem is not like other wiggle sort problems. The sequence can either start from a smaller value or bigger value. That is, it can be something like [1,2,1] or [2,1,2]. Those 2 conditions may give you different answers. That is why you need take it into account to solve the problem. In my code, I use a var called "bs" (big small) to mark if the a bigger value or smaller value is needed for the current step. Giving different initial value to this var will handle those 2 different conditions.

    2. When you are looking for the next value which is valid to the sequence, you may want to be greedy. That means if you are looking for the next value which is the bigger one, you want to find the biggest one in the neighborhood. For the smaller one, find the smallest.
      For instance, the array given is [3,2,1,2,4].
      The Initial value of "bs" is -1. (Find the first smaller value.) And 1 will be picked. That is because 3,2,1 are monotonically decreasing and from greedy, the smallest value is wanted here to get a "higher" chance to be smaller than the bigger one.
      If "bs" is 1, pick the biggest one of the monotonically increasing sequence.

    3. Once one "smallest" or "biggest" value is hit. Toggle the value of "bs" to make the sequence is one smaller one bigger or one bigger one smaller. And done!

    public int wiggleMaxLength(int[] nums) {
        if(nums.length==0) return 0;
        return Math.max(longestsub(-1,nums),longestsub(1,nums));
    }
    private int longestsub(int bs, int[] nums){
        int maxlen = 1;
        for(int i = 0 ;i+1<nums.length;i++){
            if(bs==-1){ //mark if a bigger or smaller value is needed -1 for smaller, 1 for bigger
                if(nums[i]<nums[i+1]){
                    maxlen+=1;
                    bs = 1;
                }
            }
            if(bs==1){
                if(nums[i]>nums[i+1]){
                    maxlen+=1;
                    bs = -1;
                }
            }
        }
        return maxlen;
    }

Log in to reply
 

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