My C++ O(n) Solution With Good Explanation


  • 4

    The key of my solution is to eliminate backtrace and that can be achieved by introducing a decrease array, which stores the length of degressive sub arrary starting from any index.

    For example, if the ratings array is [ 5, 1, 2, 3, 4, 9, 5, 3, 2, 2, 8 ], it's corresponding decrease array should look like this: [ 2, 1, 1, 1, 1, 4, 3, 2, 1, 1, 1 ]. sub array [ 9, 5, 3, 2 ] is degressive and its length is 4, that's where the 4 comes from. Any single-element sub array can make a degressive array of length 1. Obviously, this decrease array can be easily created by scanning ratings array from tail to head.

    With this decrease array constructed, we can calculate candies for each child without backtrace.

    int candy(vector<int>& ratings) {
        if( ratings.empty()) return 0;
        vector<int> decrease(ratings.size());
        decrease[ratings.size()-1] = 1;
        for( int i=ratings.size()-2; i>=0; i-- ) {
            if( ratings[i] > ratings[i+1] ) decrease[i] = decrease[i+1]+1;
            else decrease[i] = 1;
        }        
        vector<int> candy(ratings.size());
        candy[0] = decrease[0];
        int sum = candy[0];
        for( int i=1; i<ratings.size(); i++ ) {
            if( ratings[i] > ratings[i-1] ) candy[i] = max( decrease[i], candy[i-1]+1);
            else if( ratings[i] == ratings[i-1] ) {
                candy[i] = max( decrease[i], 1);
            }
            else candy[i] = min(candy[i-1]-1, decrease[i]);
            sum += candy[i];
        }
        return sum;
    }
    

    And, if you want to save more space, you can reuse the decrease array.

    int candy(vector<int>& ratings) {
        if( ratings.empty()) return 0;
        vector<int> decrease(ratings.size());
        decrease[ratings.size()-1] = 1;
        for( int i=ratings.size()-2; i>=0; i-- ) {
            decrease[i] = ratings[i] > ratings[i+1] ? decrease[i+1] + 1 : 1;
        }        
        int sum = decrease[0];
        for( int i=1; i<ratings.size(); i++ ) {
            if( ratings[i] > ratings[i-1] ) 
                decrease[i] = max( decrease[i], decrease[i-1]+1);
            else if( ratings[i] == ratings[i-1] ) 
                decrease[i] = max( decrease[i], 1);
            else 
                decrease[i] = min(decrease[i-1]-1, decrease[i]);
            sum += decrease[i];
        }
        return sum;
    }

Log in to reply
 

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