题目链接：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?

这道题的要求是：N个孩子站成一排，每个孩子有等级数值标识。给每个孩子发糖，要求每个孩子至少1块糖，而且如果孩子等级比两边的高，那么他的糖也要比两边的多。计算最少需要发出多少糖。

根据题意，如果当前孩子i的等级比i-1和i+1的高，那么给i发的糖就应该是给i-1和i+1的糖的较大值加1；否则，给i发1块糖。可是，有1个问题，就是对于孩子i，不知道其右边的孩子（即i+1）分到了多少糖。因此，可以考虑先对数组遍历2遍：

  • 第一遍，从左到右，记录糖的数量在v1中。当前孩子与其左边比较，如果等级高的话，糖的数量就是左边孩子糖的数量加1；否则，就分1块糖；
  • 第二遍，从右到左，记录糖的数量在v2中。当前孩子与其右边比较，如果等级高的话，糖的数量就是左边孩子糖的数量加1；否则，就分1块糖。

接下来再累加v1和v2这两个数组中对应位置的较大值即可。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution
{
public:
    int candy(vector<int> &ratings)
    {
        int n = ratings.size();
        if(n == 0)
            return 0;
        
        vector<int> v1(n), v2(n);
        v1[0] = 1, v2[n - 1] = 1;
        
        for(int i = 1; i < n; ++ i)
            v1[i] = ratings[i] > ratings[i - 1] ? v1[i - 1] + 1 : 1;
        for(int i = n - 2; i >= 0; -- i)
            v2[i] = ratings[i] > ratings[i + 1] ? v2[i + 1] + 1 : 1;
        
        int res = 0;
        for(int i = 0; i < n; ++ i)
            res += max(v1[i], v2[i]);
        return res;
    }
};