Java O(n) & O(1). concise


  • 1
    D
    public int candy(int[] ratings) {
    	if (ratings.length == 0) {
    		return 0;
    	}
    	int res = 1;
    	int pre = 1; // candies of previous
    	int j = 0; // start point of descending sequence
    	int preJ = 1; // candies of j
    	for (int i = 1; i < ratings.length; i++) {
    		if (ratings[i] == ratings[i - 1]) {
    			pre = 1;
    			j = i;
    			preJ = pre;
    		} else if (ratings[i] > ratings[i - 1]) {
    			pre++;
    			j = i;
    			preJ = pre;
    		} else {
    			res += i - j - 1;
    			if (i - j + 1 > preJ) { // if start point is large enough than all these descending, no need to add 1. otherwise add 1 to starting point
    				preJ = i - j + 1;
    				res++;
    			}
    			pre = 1;
    		}
    		res += pre;
    	}
    	return res;
    }

Log in to reply
 

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