A simple solution with one loop(C++ O(n))


  • 0
    M
    class Solution {
        public:
            int candy(vector<int>& ratings) {
                int sum = 0;
                int downCount = 0;
                int candyCount = 1;
            
                vector<int>::iterator prev = ratings.begin();
                
                for (vector<int>::iterator current = prev; current != ratings.end() ; ++current) {
                    int shift = *current - *prev;
                    if (shift < 0) {
                        sum += --candyCount;
                        downCount++;
                    }else{
                        if (downCount > 0) {
                            int addition = candyCount < 1 ? 1 : 0;
                            sum += (groupCount+addition) * (1 - candyCount);
                            downCount = 0;
                            candyCount = 1;
                        }
                        if( shift > 0 ){
                            sum += ++candyCount;
                        }else{
                            candyCount = 1;
                            sum += candyCount;
                        }
                    }
                    prev = current;
                }
                
                if (groupCount > 0) {
                    int addition = candyCount < 1 ? 1 : 0;
                    sum += (groupCount+addition) * (1 - candyCount);
                }
                return sum;
            }
    };
    

Log in to reply
 

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