[Leetcode] 135. 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?

思路：

本题的总体策略还是贪心法。我开始的思路是：将小孩子们按照rating的升序进行排序，然后依次分配糖果：如果他的某个邻居或者两个邻居已经分配糖果了并且他的rating不大于他的邻居的rating（不可能小于的），那么分配和他的邻居相同数目的糖果；如果他的rating高于他的某个邻居，那么分配他的邻居糖果数目+1。如果他的邻居尚未分配糖果，则只给分配1个。这个思路是可行的，但是代码复杂，时间复杂度为O(nlogn)，空间复杂度O(n)。

采用两边扫描的方法可以将时间复杂度降为O(n)。具体方法如下：先从左往右扫描一遍，如果后面一个比前面大，那么他分配的就多一颗糖果，否则就是1。但是这样会产生一个情况，就是两个相邻的排名一样，那么后一个还是分一个，但是右面的小孩的rating可能比这个还小，但是仍然分得和这个值一样的糖果，因此还要从右往左再扫描一遍来补偿小的值。这个思路的代码更加精简，时间复杂度是O(n)，空间复杂度O(n)。

代码：

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.size() == 0) {
            return 0;
        }
        int len = ratings.size(), ret = 0;
        vector<int> nums(len, 1);
        for (int i = 1; i < len; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                nums[i] = nums[i - 1] + 1;
            }
        }
        for (int i = len - 1; i > 0; --i) {
            if (ratings[i - 1] > ratings[i] && nums[i - 1] <= nums[i]) {
                nums[i - 1] = nums[i] + 1;
            }
            ret += nums[i];
        }
        return ret + nums[0];
    }
};