C++ solution ,using recursion , 50ms, clear enough


  • -1
    B
    int calculate(vector<pair<int,int>> & ob,int i)   // the recursion function
    {
    	if (ob[i].second!=0)
    	{
    		return ob[i].second;
    	}
    	else if (ob.size()==1)
    	{
    		return ob[0].second = 1;
    	}
    	else if (i==0)   // the left boundary
    	{
    		if (ob[i].first<=ob[i+1].first)
    		{
    			return ob[i].second = 1;
    		}
    		else
    		{
    			return (ob[i].second = calculate(ob, i + 1) + 1);
    		}
    	}
    	else if (i==ob.size()-1)     // the right boundary
    	{
    		if (ob[i].first <= ob[i - 1].first)
    		{
    			return ob[i].second = 1;
    		} 
    		else
    		{
    			return (ob[i].second = calculate(ob, i - 1) + 1);
    		}
    	}
    	else   // the middle ones should consider it's left neighbour and it's right neighbour
    	{
    		if ((ob[i].first <= ob[i + 1].first) && (ob[i].first <= ob[i - 1].first))
    		{
    			return ob[i].second = 1;
    		}
    		else if ((ob[i].first <= ob[i + 1].first))
    		{
    			return (ob[i].second = calculate(ob, i - 1) + 1);
    		}
    		else if ((ob[i].first <= ob[i - 1].first))
    		{
    			return (ob[i].second = calculate(ob, i + 1) + 1);
    		}
    		else
    		{
    			return (ob[i].second = (max(calculate(ob, i - 1), calculate(ob, i + 1)) + 1));
    		}
    	}
    }
    
    int candy(vector<int>& ratings) {
    	vector<pair<int, int>> ob;
    	for (vector<int>::iterator it = ratings.begin(); it != ratings.end(); it++)
    	{
    		ob.push_back(pair<int, int>(*it, 0));
    	}
    	int sum = 0;
    	for (int i = 0; i < ob.size();i++)
    	{
    		if (ob[i].second==0)
    		{
    			calculate(ob, i);
    		}
    		sum += ob[i].second;
    	}
    	return sum;
    }

Log in to reply
 

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