Java simple greedy 0ms solution with explanation


  • 0

    -------- Updated --------

    While after thinking a while, I find the idea behind this problem is to count continuous "up"s and "down"s. So the solution could be more concise and simple compared with my original solution.

    public class Solution {
      public int wiggleMaxLength(int[] nums) {
        if(nums.length<2) return nums.length;
        int up=0, down=0, pre = -1;
        for(int i=1;i<nums.length;i++){
          if(nums[i]>nums[i-1] && pre!=1){
            up++;
            pre = 1;
          }
          if(nums[i]<nums[i-1] && pre!=0){
            down++;
            pre = 0;
          }
        }
        return 1+up+down;
      }
    }
    

    -------- Original Post --------

    The idea is simple: greedily choose or not choose current element to form the final wiggle subsequence. Greedy strategy: update current element with the greater or smaller element according to ⬆️ or ⬇️

    public int wiggleMaxLength(int[] nums) {
      if(nums.length<2) return nums.length;
      int ret = 1, pre = nums[0], i=1;
      boolean preUp = nums[i]>nums[i-1]?true:false;
      for(;i<nums.length;i++){
        if(nums[i]==nums[i-1]) continue;
        if(i==1) ret++;
    //if wiggle, add ret, update pre and preUp
        if( (preUp == true && nums[i]<pre) || (preUp == false && nums[i]>pre)){
          ret++;
          preUp = !preUp;
          pre = nums[i];
        }
    //if not wiggle, keep preUp and update pre (if needed)
        else{
          if(preUp==true)
            pre = pre>nums[i]?pre:nums[i];
          else
            pre = pre<nums[i]?pre:nums[i];
        }
      }
      return ret;
    }
    

Log in to reply
 

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