135 - Candy

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?

Hide Tags

Greedy

这道题很早以前看了一眼，没大明白问的啥东东，后来就一直放着没动。
刚刚仔细读了一下，好像知道了，就在纸上比划了几个数组，猜想应该是这么回事：
首先每人至少应该有一颗糖，所以基数是总共小孩的个数。

然后从头向尾逐个检查，是不是比前一个rating value大？大的话，就要追加糖果了。
     追加的时候要注意，如果是连续出现递增的情况，后一个小孩追加的糖果的个数，要比前一个更多一个，
     因此，需要弄一个临时变量表示当前这个小孩应该追加几个糖果，并让它随着 rating value 递增而递增；
     另外，一旦出现下降，这个临时变量就要清零，从下一个递增的地方重新累积。

再然后就从尾向头检查，看是不是前一个比后一个大，是的话，也要增追加糖果。（也需要一个临时变量来累加）
    但此时有一个特别的情况，就是对于处于波峰位置的局部最大值：
          前面的扫描过程中，它已经被追加了糖果了，此时如果重复追加，可能就给多了；
          但前面的扫描追加的值，可能不能完全体现它与自己后面的小孩的 rating value 之间的关系。
          例如 [3,1,9,8,7,2]，从前向后检查的话，[9] 只会被追加一个；单从后向前检查的话，它应该被追加3个
          因此，这时候需要知道前一次扫描追加了多少，并且跟当前的临时变量比较。
          如果新的临时变量大，就取新的临时变量的值，但是需要减去之间已经追加过的值；
          如果之前追加的值更大，则无需再追加。
     这也就意味着，还需要一个辅助数组来记录之前追加过的内容，以便比较，因此额外使用了一个数组 buf。

按照这个逻辑试了一下，确实没有问题，两轮扫描之后即可直到最少需要多少颗糖果。
第二次扫描的时候，最初的逻辑如下：
        if(!ii)
            added++, rst += added;
        else
        {
            if(ratings[ii-1]<ratings[ii])
                added++, rst += (added>buf[ii])?(added-buf[ii]):0;
            else
                added++, rst += added;
        }
合并代码之后的逻辑如下面蓝色部分所示。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int sz=ratings.size();
       
        int rst=sz, added=0, buf[sz]={0};
        for(int ii=1; ii<sz; ++ii)
        {
            if(ratings[ii]>ratings[ii-1])
                added++, rst += added, buf[ii]=added;
            else
                added=0;
        }
       
        added=0;
        for(int ii=sz-2; ii>=0; ii—)
        {
            if(ratings[ii]>ratings[ii+1])
            {
                added++;
                rst += (ii && ratings[ii-1]<ratings[ii]) ?
                            ((added>buf[ii])?(added-buf[ii]):0) : added;
            }
            else
                added=0;
        }
        return rst;
    }
};
36 ms.