###### tags: `LeetCode` `Greedy Algorithm` `Hard`
# LeetCode #135 [Candy](https://leetcode.com/problems/candy/)
### (Hard)
老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分。
你需要按照以下要求，幫助老師給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果。
評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果。
那麼這樣下來，老師至少需要準備多少顆糖果呢？

---
使用貪心法則, 遍歷數組兩次。

第一次, 每個小孩若比他左邊的小孩評價高, 則必須拿到比左邊小孩的糖果數多1的糖果; 第二次則與右邊相比。

由於兩次比較都是確保小孩能拿到的最低糖果數, 所以最後得到的答案就是最小值。

---

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