My easy-understand Java solution in O(n)time and O(1)space with explanation


  • 0
    G
    public class Solution {
        public static int candy(int[] ratings){
    		int result = 1,length = ratings.length,cur = 1;;
    		for(int i=1;i<length;){
    			if(ratings[i]>ratings[i-1]){
    				while(i<length&&ratings[i]>ratings[i-1]){
    					cur++;
    					result += cur;
    					i++;
    				}
    			}
    			if(i<length&&ratings[i]==ratings[i-1]){
    				while(i<length&&ratings[i]==ratings[i-1]){
    					i++;
    					result++;
    					cur = 1;
    				}
    			}
    			if(i<length&&ratings[i]<ratings[i-1]){
    				int index = i;
    				while(i<length&&ratings[i]<ratings[i-1]){
    					cur--;
    					result += cur;
    					i++;
    				}
    				if(cur<1){
    					result += (1-cur)*(i-index+1);
    				}
    				else if(cur>1){
    					result += (1-cur)*(i-index);
    				}
    				cur = 1;
    			}
    		}
    		return result;
    	}
    }
    

    There are three coditions,>/==/<.Two of them,< and == is easy to understand.When it comes to >,we need to get the index where start descending,and when it turns back to ascend,we can add the D-value.


Log in to reply
 

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