Runtime of my java solution is about 400, who has 200-300ms way of solving it?

  • 0
    public int candy(int[] ratings) {
        int n = ratings.length;
        if(n<2) return n;
        int k=0,state=0,temp=0;
        int result = n;
        for(int i=0;i<n-1;i++){
                temp = (state==2)?k:(state==1)?0:temp;
                k = (state!=0)?0:k;
                state = 0;
                result += ++k;
                if(k<=temp) result--;
            }else if(ratings[i]==ratings[i+1]){
                if(state != 1) state = 1;
                k = (state!=2)?0:k;
                state = 2;
                result += ++k;
        return result;

  • 0

    my thoughts are pretty straightforward, there are three states in this question:
    state=0, ratings go all the way down;
    state=1, ratings equal;
    state=2, ratings go all the way up;
    the only thing I have to pay attention to is if state goes from state 2 to 0, which forms a peak, then the peak should has more candies than both neighbors, which I keep track of the left side value, if the right side doesn't exceed , then the peak value doesn't need to add up.

    this runtime is over 400ms, and i can see that most solutions are 200-300ms, so anyone would like to share that with me? thanks

Log in to reply

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