LeetCode || Candy

Candy

Total Accepted: 12392 Total Submissions: 68386My Submissions

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?

特例：ratings为：1,3,3,4,3,2,1,0。那么candy数量应该为：1+2+2+5+4+3+2+1=20。分析当中的规律，rating相等的两个邻居candy数能够不等。我们仅仅须要关注序列中连续的递减子序列的长度就可以，比方本例中的 4,3,2,1,0，到达前四个人1,3,3,4显然我们分别应该给予1,2,3,4个candy，遇到第五个人3时，与前邻居4比是递减的。我们也给它1个。可是此时由于前邻居是4个，故不用加；接下来看2。我们给它1个，前邻居3也是1个，故应该给它加1个。可是前前邻居4是4个。故不用加；以此类推。。

。

由上述分析能够看出。我们须要记录递减子序列的长度descLen。以及子序列开头第一个人的candy数量descBegCan，在推断当前属于递减子序列的人的candy数时。我们并不能只给当前candy总数加上这个长度，由于可能递减子序列的开头那个人(不过开头这个人)本身已经有非常多candy了。那么它不须要加1（就像上面推断到第五六个人3,2时。我们并不须要给第四个人4的candy数加1，由于它已经有了3个了。3>2>1 成立）。而要看当前的长度descLen与descBegCan的大小关系。假设长度小于开头那个人的数量。那么仅加上长度减1 就可以；假设二者相等。那么须要加上长度。

代码例如以下：

class Solution {
public:
    int candy(vector<int> &ratings) {
        int res=0;
        int lastRat = -1, lastCan = 0,  can = 0;
        int descLen = 0, descBegCan=0;  //连续递减子序列的长度和递减序列头部的值
        for(int i=0; i<ratings.size(); ++i){
            if(ratings[i]>lastRat){
                can = lastCan+1;
                descLen = 0;
            }else if(ratings[i]==lastRat){  //相邻且rating相等的人candy能够不一样
                can = 1;
                descLen = 0;
            }else{
                can = 1;
                if(descLen==0)
                    descBegCan = lastCan;
                descLen++;
                
                if(can==lastCan){
                    if(descLen<descBegCan)
                        res += descLen-1;
                    else if(descLen==descBegCan){
                        res += descLen;
                        descBegCan++;
                    }
                }
            }
            res += can;
            lastRat = ratings[i];
            lastCan = can;
        }
        return res;
    }
};

本方法的空间复杂度为O(1)，时间复杂度为O(n)。应该属于最好的方法之中的一个了。