C++ solution with different thinking


  • 0
    S
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            if(ratings.size() == 1) return 1;
            
            int len = ratings.size();
            vector<int> candies(len, 1);
            int peak=0, valley=0;
            int direct = 0; // -1: down; 1: up; 0: parallel
            int i;
            for(i=0; i<len; i++)
            {
                if(direct == 1)
                {
                    if(i==len-1 || ratings[i] >= ratings[i+1]) // turn to down/parallel, found 'peak'
                    {
                        peak = i;
                        // from valley forward to peak
                        for(int x=valley; x<=peak; x++)
                            candies[x] = candies[x] + (x - valley);
                        
                        if(i==len-1) continue;
                        if(ratings[i] > ratings[i+1]) direct = -1;
                        else direct = 0;
                    }
                }
                else if(direct == -1)
                {
                    if(i==len-1 || ratings[i] <= ratings[i+1]) // turn to up/parallel, found 'valley'
                    {
                        valley = i;
                        // from valley back to peak
                        for(int x=valley; x>=peak; x--)
                            candies[x] = max(candies[x],(valley-x+1));
    
                        if(i==len-1) continue;
                        if(ratings[i] < ratings[i+1]) direct = 1;
                        else direct = 0;
                    }
                }
                else if(direct == 0)
                {
                    peak = i; valley = i;
                    if(i==len-1) continue;
                    if(ratings[i] > ratings[i+1]) direct = -1;
                    if(ratings[i] < ratings[i+1]) direct = 1;
                    if(ratings[i] == ratings[i+1]) direct = 0;
                }
            }
            int sum=0;
            for(int i=0; i<candies.size(); i++)
                sum += candies[i];
            return sum;
        }
    };

Log in to reply
 

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