An easy-understood O(n) solution in C++


  • 0
    L

    if ratings[i]>ratings[i-1], candy[i]=candy[i-1]+1, (candy[i] denote the number of candies of the ith boy), record the position and candy[i];
    if ratings[i]==ratings[i-1], candy[i]=1, record the position and candy[i];
    if ratings[i]<ratings[i-1], make candy[i]=1, if candy[i-1]==1, it shows that candy[i-1]is not enough, we need to add 1 from candy[position+1] to candy[i-1], at the same time , candy[position]--, if candy[position]==1, it shows that candy[position]is not big enough,candy[position] needs to add 1.

    int candy(vector<int> &ratings) 
    {   
    	int sum = 1;
    	int num = 1;
    	int pos = 0;
    	int d = 1;
    	int i;
    	for (i=1; i!=ratings.size(); i++)
    	{
    		if (ratings[i] > ratings[i - 1])
    		{
    			sum+=++num;
    			pos = i;
    			d = num;
    		}
    		else if (ratings[i] == ratings[i - 1])
    		{
    			sum++;
    			num = 1;
    			pos = i;
    			d = 1;
    		}
    		else if (ratings[i] < ratings[i - 1])
    		{
    			if (num == 1)
    			{
    				if (d == 1)sum += i - pos + 1;
    				else
    				{
    					sum += i - pos;
    					d--;
    				}
    			}
    			else
    			{
    				sum++;
    				num = 1;
    				d--;
    			}
    		}
    	}
    	return sum;
    }

Log in to reply
 

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