135.Candy

Tags: Hard Greedy

Links: https://leetcode.com/problems/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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

---

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> num(n, 1);

        for (int i = 0; i < n - 1; ++i){
            if (ratings[i + 1] > ratings[i]) num[i + 1] = num[i] + 1;
        }

        for (int i = n - 1; i > 0; --i){
            if (ratings[i - 1] > ratings[i])
                num[i - 1] = max(num[i - 1], num[i] + 1);
        }

        return accumulate(num.begin(), num.end(), 0);
    }
};

第一遍从左向右遍历，如果右边的小朋友的等级高，右边加一个糖果，这样保证了一个方向上高等级的糖果多。然后再从右向左遍历一遍，如果相邻两个左边的小朋友等级高，而左边的糖果又少的话，则左边糖果数为右边糖果数加一。最后再把所有小朋友的糖果数都加起来返回即可。时间复杂度$O(n)$， 空间复杂度$O(n)$。

class Solution {
public:
    int candy(vector<int>& ratings) {
        std::ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);

        if (ratings.empty()) return 0;
        int res = 1, pre = 1, cnt = 0;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] >= ratings[i - 1]) {
                if (cnt > 0) {
                    res += cnt * (cnt + 1) / 2;
                    if (cnt >= pre) res += cnt - pre + 1;
                    cnt = 0;
                    pre = 1;
                }
                pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
                res += pre;
            } else {
                ++cnt;
            }
        }     
        if (cnt > 0) {
            res += cnt * (cnt + 1) / 2;
            if (cnt >= pre) res += cnt - pre + 1;
        }
        return res;
    }
};

首先在输入和输出上用了点技巧，主要是因为输入流和输出流绑定了造成性能问题（改进后时间减少8ms）。另外一点是，和上面需要从左到右扫描两遍不同，我们只需要扫描一遍。

注：比较的大小是点的权值。

考虑当前点，思考它之前和之后的点，对于后面的点，可能相等、小于或大于三种情况，前面的点也是三种情形。后面的情形未知，但是前面的点因为已经访问过了，所以应该充分利用前面的信息，那么判断的依据来自于当前点以前的点。

（1）如果当前点不小于前面点，也就是序列上升的情形，但是相等和严格大于又不同。等于时候，当前点只需分配一块糖就满足条件；严格大于就需要+1。

（2）如果当前点小于前面点，说明是递减序列，因为不确定后面是否还会继续递减，暂时不确定当前点究竟该分配多少糖。所以可以首先考虑用一个bool型来标记，但是又因为需要知道这个递减的序列到底有多长以便计算总和，所以应该利用一个int cnt来记录，没有递减就为0，递减了值就大于0。

然后开始计算糖的总数，尤其是需要考虑前面的点分配的糖数，很容易想到需要一个pre来记录，这个pre对于（1）情形来说，就是当前点的最邻近的点，对于（2）来说，应该是序列刚开始递减的那个点的数值。因为开始递减的时候，对应的点数量是要增加的，递减序列的最高点需要比较从最低点到序列顶点递增后的数值和原本就有的数值，取两者中较大者。由于考虑总数，只需要加上两者差值。

最后就是考虑边界条件，序列尾端的时候需要做一下后处理。