Greedy: One Pass, O(n) time, O(1) space, No Multiplication Solution


  • 0
    G
    public int candy(int[] ratings) {      
        int sum = 1, x = 1, peek = 1;
        /*peek: number of candies the start child in the current down sequence */
    	boolean up = false;
    	for (int i = 1; i < ratings.length; i++) {
    		if (ratings[i-1] > ratings[i]) {
    			if (!up) { 
    				sum += (x == peek - 1) ? (x = ++peek) : ++x;
    			} else {   // up to down
    				peek = x;
    				sum += (x = 1);
    			}
    			up = false;
    		} else if (ratings[i-1] < ratings[i]) {
    			sum += (up) ? ++x : (x = 2);
    			up = true;
    		} else { 
    			peek = 1;
    			sum += (x = 1);
    			up = false;
    		}
    		
    	}
    	return sum;
    }

Log in to reply
 

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