C++ clean one pass solution O(1) space


  • 0
    int candy(vector<int>& ratings) {
            int n = ratings.size(), sum = 1, count = 0, candy = 1;
            for (int i = 1; i < n; ++i) {
                if (ratings[i] > ratings[i - 1]) 
                    candy += 1;
                else if (ratings[i] == ratings[i - 1])
                    candy = 1;
                else {
                    candy -= 1;
                    count++; 
                }
                sum += candy;
                // check if it's the end of the decreasing sequence
                if (ratings[i] < ratings[i - 1] && (i == n - 1 || ratings[i] <= ratings[i + 1])) {
                    // the length of the decreasing sequence is count + 1
                    // if candy less than 1, we should increase the peak
                    // if candy more than 1, we shouldn't decrease the peak because the it's also
                    // the peak of the previous increasing sequence
                    sum += (1 - candy) * (candy > 1 ? count : count + 1);
                    candy = 1; 
                    count = 0;
                }
            }
            return sum;
        }
    

Log in to reply
 

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