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?

分析如下：

開出一個O(n)大小的數組，用來記錄每個小孩的那糖數，因為每個小孩至少要拿1顆糖，是以數組元素初始化為1.

case 1. 假設有小孩A, B ， rating分别是{1,1},顯然每個人各拿1顆糖就夠，顯然每個人拿糖顆數是{1, 1}，最後答案為2.

case 2. 假設有小孩A, B, C, D, rating分别是{10, 32, 43, 55}, 那麼每個人拿糖的顆數依次為{1, 2, 3, 4},最後答案為10. 這說明可以順序掃描數組，找到一個遞增序列，拿糖數從1開始遞增。比如這裡找到了遞增序列A, B, C, D, 拿糖數從A = 1開始依次遞增。

case3. 假設有小孩A, B ,C ,D E, F, rating 分别是{10, 32, 43, 55, 40, 11}, 那麼每個人拿糖顆數是 {1, 2, 3, 4, 2, 1}， 這說明可以在順序掃描數組之後，再反序掃描數組，得到反序掃描數組時的遞減序列。比如順序掃描了A, B ,C, D, E, F之後，得到{1, 2, 3, 4, 1, 1,}，之後再反序掃描數組，找尋遞增數列，每段遞增數列的拿糖顆數也從1開始遞增。反序掃到F，得到F=1, 掃到E 因為E> F, 是以E = 2。掃到D，因為D> E ,是以D= 3，但是其實這裡的D和E， F不一樣，D是之前順序掃描時候已經被指派過的值，D= 4，而反序掃描的時候，

D= 3， 顯然隻能取大值才能滿足要求。是以反序掃描的時候，如果遇到已經在順序掃描中指派的小孩，要兩個值中取較大的值。

上面描述的是貪心算法的思想。

我的代碼：

//38ms
class Solution {
public:
    int candy(vector<int> &ratings) {
        if (ratings.size() <= 1) return 1;
        
        int sum = 0;
        vector<int> assign(ratings.size(), 1);
        
        for (int i = 1; i < assign.size(); ++i) {
            if (ratings[i] > ratings[i - 1]) {
                if (assign[i-1] + 1 > assign[i]) {
                    assign[i] = assign[i-1] + 1;
                }
            }
        }
        
        for (int i = assign.size() - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                if (assign[i+1] + 1 > assign[i]) {
                    assign[i] = assign[i+1] + 1;
                }
            }
        }
        
        for (int i = 0; i < assign.size(); ++i)
            sum += assign[i];
        return sum;
    }
};