LeetCode－135. Candy

難度:Hard

描述:有 n 個孩子站成一行。每個孩子都被分配了一個整數陣列 ratings 中給定的評分值。

你要按照以下要求給這些孩子發糖果：

每個孩子至少得到一顆糖果。

評分較高的孩子會比他們的鄰居得到更多的糖果。

返回你需要準備的最少數量的糖果，以便將糖果分發給孩子們。

方法：

思路：

1.每位先發放一顆糖果。

2.左至右比對，與左方一位鄰居評分小於則保證至少大於左方一位鄰居一顆糖果。

3.右至左比對，與右方一位鄰居評分小於則保證至少大於右方一位鄰居一顆糖果。

4.合計所有糖果數量。

Runtime : 15 ms        (74.70%)

Memory : 17.78 MB  (47.60%)

  

class Solution {
public:
    int candy(vector<int>& ratings) {
        int ans = 0;
        int n = ratings.size();
        // Step 1.
        vector<int> candys(n,1);
        // Step 2.
        for(int i=1;i<n;++i){
            if(ratings.at(i-1)<ratings.at(i)){
                candys[i] = max(candys[i-1]+1, candys[i]);
            }
        }
        // Step 3.
        for(int i=n-2;i>=0;--i){
            if( ratings.at(i) > ratings.at(i+1) ){
                candys[i] = max(candys[i+1]+1, candys[i]);
            }
        }
        // Step 4.
        for(int i=0;i<n;++i){
            ans+=candys.at(i);
        }
        return ans;
    }
};