Share my Clear O(1) space JAVA solution


  • 0
    E

    From the second child, there're three situations.

    • The rating is higher than the previous.
    • The rating is equal than the previous.
    • The rating is less than the previous.

    Use the curCandy to show current candy, the preCandy shows the previous.

    • In the first situation, curCandyequals preCandy + 1, that is to say, curCandy++ ;

    • In the second situation, set curCandy = 1;

    • In the descending situation, we need to find where the descending is over. Haha, The descending list is just the reverse of a ascending list, while the candy is the same. So when the descending begins, set curCandy = 1, then every descent, curCandy++.
      However, there's a question, if the descending list is too long(the most candies in the list is more than the child before the list), result will be wrong. Check and fix it.

    Here is the code:

        public int candy(int[] ratings) {
            int len = ratings.length;
            if(len == 0) return 0;
            if(len == 1) return 1;
            int result = 1, curCandy = 1, temp;
            
            for(int i=1;i<len;){
            	if(ratings[i] > ratings[i-1]){
            		curCandy++;
            		result += curCandy;
            		i++;
            	}
            	else if(ratings[i] == ratings[i-1]){
            		curCandy = 1;
            		result += curCandy;
            		i++;
            	}
            	else{
            		temp = curCandy;
            		curCandy = 1;
            		result += curCandy;
            		while(i<len && ratings[i] < ratings[i-1]){
            			curCandy++;
            			result += curCandy;
            			i++;
            		}
            		result -= temp<curCandy?temp:curCandy;
            		curCandy = 1;
            		if(i == len)
            			return result;
            	}
            }
            
            return result;
        }
    }
    

Log in to reply
 

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