O(n)time O(1)space but a little waste of time


  • 0
    X

    class Solution {
    public:

     int candy(vector<int>& ratings) {
        if(ratings.empty())
            return 0;
        if(ratings.size()<2)
            return 1;
        int sum =ratings.size(),minadd=1;
        int index =-1,lowadd =1;
        if(ratings[0]>ratings[1])
            sum++;
        else {
            index = 0;
            if(ratings[0]<ratings[1]){sum++;lowadd++;}
            
        }
        for(int i =1;i<ratings.size()-1;i++)
        {
            if(ratings[i]>ratings[i+1])
            {
                
                if(ratings[i]<=ratings[i-1])
                {
                    if(i-index<lowadd)
                        sum+=i-index-1;
                    else sum+=i-index;
                }
            }
            else{
                index = i;
                if(ratings[i]<ratings[i+1]){
                    if(ratings[i]<=ratings[i-1])lowadd=1;
                    sum+=lowadd;
                    lowadd++;
                }
                else lowadd=1;
            }
            
        }
        
        return sum;
    }
    

    };


Log in to reply
 

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