C++ 33ms (100%) O(n)time O(1)space


  • 0
    S
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int sum=1;
            int height=0;//index of heightest rating in left
            int heightVal=INT_MAX;//val of (height-1)
            int current=1;
            for(int i=1;i<ratings.size();i++)
            {
                if(ratings[i]>ratings[i-1])
                {
                    current++;
                    heightVal=current;
                    height=i;
                    sum+=current;
                }
                else if(ratings[i]<ratings[i-1])
                {
                    int count=1;
                    if(current==1)
                        count = i-height+1;
                    else
                        height=i;
                    current=1;
                    
                    sum+=count;
                    if(count==heightVal)
                    {
                        heightVal++;
                        sum++;
                    }
                }
                else
                {
                    current=1;
                    heightVal=INT_MAX;
                    height=i;
                    sum+=current;
                }
            }
            return sum;
        }
    };
    

Log in to reply
 

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