Easy to understand Java 1ms O(n) time solution


  • 0
    S
    public static int wiggleMaxLength(int[] nums) {
        
        int len = nums.length;
        if (len < 2) {
            return len;
        }
    
        // track pos and neg solution length
        int pos = 1, neg = 1;
        // record previous status
        boolean posFlag = false, negFlag = false;
        // record previous number
        int lastPos = nums[0], lastNeg = nums[0];
        
        for (int i = 1; i < len; i++) {
            int cur = nums[i];
            if (cur != lastPos) {
                if ((cur > lastPos) ^ posFlag) {
                    pos++;
                    posFlag = !posFlag;
                }
                // update lastPos even this one is not in solution because the most recent one is easier to find next solution
                lastPos = cur;
            }
    
            if (cur != lastNeg) {
                if ((cur < lastNeg) ^ negFlag) {
                    neg++;
                    negFlag = !negFlag;
                }
                // same as Pos solution
                lastNeg = cur;
            }
        }
        return Math.max(pos,neg);
    }

  • 0

    @SmartBoyIn3716 It cannot be O(1) time.....


  • 0
    S

    @dietpepsi sorry about typo, already revised it


  • 0

    Also, you really don't need pos and neg...
    Track the longest one is enough.
    Be greedier ^_^


Log in to reply
 

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