学步园

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?

思路：

rating的趋势无非三种，上升，不变，下降。上升的话，无论上升多少rating，都加一块糖就好了。题目默认不变情况下，糖数无需满足升降趋势，因此可以按照尽量少的方式给。下降的话就不好说了。因为下降到一定程度就可能有人分不到糖了，没准还要倒贴，只好提高下降趋势发生之前的那个人的糖数。

题解：

class Solution {
public:
struct trend_t
{
    char trend;
    int len;
};

int candy(const vector<int>& ratings)
{
    auto nsum = [](const int n)->int { return n * (n + 1) / 2; };
    const auto SIZE = ratings.size();

    // special condition
    if (SIZE == 0)
        return 0;
    else if (SIZE == 1)
        return 1;

    vector<trend_t> trend;
    trend.push_back({'-', 1});
    int prev_rate = ratings[0];
    for (auto i = 1; i < SIZE; ++i)
    {
        int curr_rate = ratings[i];
        char tr = curr_rate > prev_rate ? '+' :
                  (curr_rate == prev_rate ? '=' : '-');
        if (trend.back().trend != tr)
            trend.push_back({tr, 1});
        else
            ++trend.back().len;
        prev_rate = curr_rate;
    }

    // analyze the trend
    int total_candy = nsum(trend[0].len);
    int last_candy = 1;
    for (auto i = 1; i < trend.size(); ++i)
    {
        if (trend[i].trend == '+')
        {
            total_candy += nsum(trend[i].len) + last_candy * trend[i].len;
            last_candy += trend[i].len;
        }
        else if (trend[i].trend == '=')
        {
            total_candy += trend[i].len;
            last_candy = 1;
        }
        else
        {
            if (last_candy > trend[i].len)
                total_candy += nsum(trend[i].len);
            else
                total_candy += nsum(trend[i].len) + (trend[i].len + 1 - last_candy);
            last_candy = 1;
        }
    }
    return total_candy;
}
};