Share my algorithm O(n) time, and O(1) space


  • 0
    F

    //The idea is start from some index i to some index j that ratings[i] > ratings[i+1] > ...ratings[j] <= ratings[j+1]. //Record the count (j-i+1), and calculate the sum from i to j.

    class Solution {
    public:
        int candy(vector<int> &ratings) {     
            if(ratings.size() == 0)
                return 0;           
            int resultSum = 0;
            int count = 0;
            int curLeft = 1;
            for(int i=0; i<ratings.size(); i++)
            {
                if(i<ratings.size()-1 && ratings[i]>ratings[i+1])
                    count++;
                else
                {
                    resultSum += count*(count+1)/2 + max(curLeft, 1+count);
                    int curValue;
                    if(count == 0)
                        curValue = curLeft;
                    else 
                        curValue = 1;
                    if((i<ratings.size()-1) && (ratings[i]<ratings[i+1]))
                        curLeft = curValue + 1;
                    else
                        curLeft = 1;
                    count = 0;
                }
            }
            return resultSum;
        }
    };

Log in to reply
 

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