Java one pass solution, no extra space


  • 0

    Well, my code looks a little longer because I have divided all the cases separately. It should be clear and easy to understand.

    int biggercount;
    int smallercount;
    int lastpeak;
    int total;
    public int candy(int[] ratings) {
        if(ratings.length == 0) return 0;
        if(ratings.length == 1) return 1;
        biggercount = 0; //used to record the number of children in the mono-increasing sequence
        smallercount = 0;//used to record the number of children in the mono-decreasing sequence
        lastpeak = 0;//record the number of candy needed of the highest requirement for last mono-increasing sequence
        total = 0;
        for(int i = 0;i<ratings.length;i++){
            if(i==0) continue;
            if(ratings[i]==ratings[i-1]){
                if(smallercount!=0) countsmaller();
                else if(biggercount!=0) countbigger();
                else if(smallercount==0&&biggercount==0) total++;
                lastpeak = 0;
            }
            else if(ratings[i]>ratings[i-1]){
                if(smallercount!=0){
                    countsmaller();
                    total -= 1;//or the pit value would be calculated twice.
                }
                biggercount++;
            }
            else{
                if(biggercount!=0) countbigger();
                smallercount++;
            }
            if(i==ratings.length-1){
                if(biggercount==0&&smallercount==0) total+=1;
                else if(biggercount!=0) countbigger();
                else if(smallercount!=0) countsmaller();
            }
        }
        return total;
    }
    private void countsmaller(){
        if(smallercount+1>lastpeak) total= total + calcusum(smallercount+1) - lastpeak;
        else total += calcusum(smallercount);
        smallercount = 0;
        lastpeak = 0;
    }
    private void countbigger(){
        total+=calcusum(biggercount+1);
        lastpeak = biggercount + 1;
        biggercount = 0;
    }
    private int calcusum(int k){//calculate arithmetic sequence 
        return (1+k)*k/2;
    }

Log in to reply
 

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