康瑞部落

Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.

• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

解题思路：

贪心算法，能少给就少给。最初的想法是用一个数组记录每个小孩应该给的糖果数，从左往右依次扫描，若当前小孩比左边的小孩得分高，则比左边的小孩多拿一个糖，若得分低（或相等），则只分配一个糖。但是要考虑到若左边的小孩若比自己得分高，但只有一个糖，当前小孩若比其分配的少，那么只能分配一个糖了。故可以调整左边的小孩分的糖数。维持左边已经分配的小孩的糖果数目。于是版本一的代码如下：

class Solution {
public:
    int candy(vector<int> &ratings) {
        int number = ratings.size();
        if(number == 0){
            return 0;
        }
        int* d = new int[number];   //存储前i个已经分配的糖的数目
        
        d[0] = 1;   //贪心，给第一个小孩先给一个糖
        
        for (int i=1; i<number; i++){
            if(ratings[i]<ratings[i-1]){    //当前小孩得分比左边的少，只给他一个糖，但是得修正，防止左边的已经是一个糖了
                d[i] = 1;
                for(int j=i-1; j>=0; j--){
                    if(d[j] == d[j+1] && ratings[j]>ratings[j + 1]){    //左边的小孩得分高，却只得到相同的糖，他不干了，得给他加糖
                        d[j] = d[j]+1;
                    }else{
                        break;
                    }
                }
            }else if(ratings[i] == ratings[i-1]){   //当前小孩得分与左边的相同，给他左边小孩同样多的糖
                d[i] = 1;
            }else{          //当前小孩得分比左边多，给他比左边多一个糖
                d[i] = d[i-1] + 1;
            }
        }
        
        int result = 0;
        for(int i=0; i<number; i++){
            result += d[i];
        }
        delete[] d;
        return result;
    }
};

但是出现了执行时间超时的情况。因为该方法的时间复杂度为O(n2)，特别是当小孩得分是逆序的情况，执行的最慢。

于是想其他办法。上网查了一下，终于得知，其实可以左右两边分别扫描，从左往右扫描，只需记录每个小孩相对于左边小孩所获得的糖果。从右往左扫描，只需记录每个小孩相对于右边小孩获得的糖果数，然后两个数组对应元素取较大值即为结果。下面是代码：

class Solution {
public:
    int candy(vector<int> &ratings) {
        int number = ratings.size();
        if(number == 0){
            return 0;
        }
        int* d = new int[number];   //存储前i个已经分配的糖的数目
        
        //两边扫，取较大的
        
        //从左往右扫
        d[0] = 1;   //贪心，第一个小孩先给一个糖
        for (int i=1; i<number; i++){
            if(ratings[i]<=ratings[i-1]){    //当前小孩得分比左边的少，只给他一个糖
                d[i] = 1;
            }else{          //当前小孩得分比左边多，给他比左边多一个糖
                d[i] = d[i-1] + 1;
            }
        }
        
        //从右往左扫
        int* r = new int[number];
        r[number - 1] = 1;
        for(int i = number-2; i>=0; i--){
            if(ratings[i]<=ratings[i+1]){    //当前小孩得分比右边的少，只给他一个糖
                r[i] = 1;
            }else{          //当前小孩得分比右边多，给他比右边多一个糖
                r[i] = r[i+1] + 1;
            }
        }
        
        int result = 0;
        for(int i=0; i<number; i++){
            result += (d[i]>r[i]?d[i]:r[i]);
        }
        delete[] r;
        delete[] d;
        return result;
    }
};

上述代码中，只扫描了两遍，所以时间复杂度为O(n)，用的空间为2*n。可以优化一下代码，使得用的空间为n，如下所示：

class Solution {
public:
    int candy(vector<int> &ratings) {
        int number = ratings.size();
        if(number == 0){
            return 0;
        }
        int* d = new int[number];   //存储前i个已经分配的糖的数目
        
        //两边扫，取较大的
        
        //从左往右扫
        d[0] = 1;   //贪心，第一个小孩先给一个糖
        for (int i=1; i<number; i++){
            if(ratings[i]<=ratings[i-1]){    //当前小孩得分比左边的少，只给他一个糖
                d[i] = 1;
            }else{          //当前小孩得分比左边多，给他比左边多一个糖
                d[i] = d[i-1] + 1;
            }
        }
        
        int result = 0;
        int lastCandyNumber = 1;    //从右往左扫面上一个孩子的糖果数目
        result += (d[number-1]>lastCandyNumber?d[number-1]:lastCandyNumber);
        //从右往左扫
        for(int i = number-2; i>=0; i--){
            if(ratings[i]<=ratings[i+1]){    //当前小孩得分比右边的少，只给他一个糖
                lastCandyNumber = 1;
            }else{          //当前小孩得分比右边多，给他比右边多一个糖
                lastCandyNumber++;
            }
            result += (d[i]>lastCandyNumber?d[i]:lastCandyNumber);
        }
        
        delete[] d;
        return result;
    }
};

相关的若与左右两边有关的问题，都可以考虑两边扫的方法。

二次刷题2015-10-10

class Solution {
public:
    int candy(vector<int>& ratings) {
        int result=0;
        
        int len = ratings.size();
        if(len == 0){
            return result;
        }
        vector<int> numsLeft(len, 0);
        numsLeft[0] = 1;
        for(int i = 1; i<len; i++){
            if(ratings[i]>ratings[i-1]){
                numsLeft[i] = numsLeft[i-1] + 1;
            }else{
                numsLeft[i] = 1;
            }
        }
        vector<int> numsRight(len, 0);
        numsRight[len-1] = 1;
        for(int i = len-2; i>=0; i--){
            if(ratings[i]>ratings[i+1]){
                numsRight[i] = numsRight[i+1] + 1;
            }else{
                numsRight[i] = 1;
            }
        }
        
        for(int i = 0; i<len; i++){
            result += max(numsLeft[i], numsRight[i]);
        }
        
        return result;
    }
};