Constant-space Java solution in one pass


  • 1
    M

    Give 1st child one candy. For the subsequent children, cope with as follows:
    assuming the child i - 1 have been allocated candies, then the next child (child i) will be allocated candies as one of the following ways:
    (1) when ratings[i] == ratings[i-1], one candy ;
    (2) when ratings[i] > ratings[i-1], 1 + the candies of previous child (child i-1) ;
    (3) when ratings[i] < ratings[i-1], count length of the continuous decrease array (mark as len), and we could figure out the sum of candies for child i-1, i, i+1, i -1 + len -1.

    The pattern indicates the idea of this solution.

           &
         &    
       &
     & & & & &
       &
         &
           &
    
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0)
            return 0;
            
        int totalCnt = 1;
        int preCandyCnt = 1; //previous child's candy number
        int i = 1;
        while (i < ratings.length){
            if (ratings[i] == ratings[i-1]){
                totalCnt += 1;
                preCandyCnt = 1;
                i++;
            }else if (ratings[i] > ratings[i-1]){
                totalCnt += preCandyCnt+1;
                preCandyCnt = preCandyCnt+1;
                i++;
            }else{
                //desent length of Array from i-1, lenth is j - (i-1)
                int j = i;
                while(j < ratings.length && ratings[j] < ratings[j-1])
                    j++;
                int lenDesc = j - (i-1);
                
                if (preCandyCnt < lenDesc)
                    totalCnt += lenDesc-preCandyCnt;
                totalCnt += (lenDesc-1 + 1) * (lenDesc-1) / 2;
                preCandyCnt = 1;    
                i = j;
            }
        }
        return totalCnt;
    }

Log in to reply
 

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