O(n) c++ solution


  • 0
    M
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int i, n, sum;
            n = ratings.size();
            vector<int> candy(n, 1);
            
            for(i = 1; i < n; i++){
                if(ratings[i] > ratings[i - 1]){
                    candy[i] = candy[i - 1] + 1;
                }
            }
            sum = candy[n - 1];
            for(i = n - 2; i >= 0; i--){
                if(ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]){
                    candy[i] = candy[i + 1] + 1;
                }
                sum += candy[i];
            }
            return sum;
        }
    };
    

    This is a two-pass checking. Starting from the beginning, give one more candy to a kid if his rating is higher than the kid before him. Then start again from the end. The idea is simple :)


Log in to reply
 

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