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


  • 0
    K
    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++){
            if(ratings[i]>ratings[i+1]){
                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;
            }else{
                k = (state!=2)?0:k;
                state = 2;
                result += ++k;
            }
        }
        return result;
    }

  • 0
    K

    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.