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?

• idea

  1. 首先将每个孩子的candy数组ans设置为1。
  2. 从前往后，假如当前孩子比前一个孩子的rating高，则当前孩子的ans为前一个孩子的ans+1
  3. 从后往前，假如当前孩子比前一个孩子的rating高且当前孩子的ans小于等于后一个孩子的ans，则当前孩子的candy为后一个孩子的ans+1
  4. 使用accumulate累加ans

• code

#include <bits/stdc++.h>

class Solution {
public:
    int candy(vector<int> &r) {
        int n = r.size();
        vector<int> ans(n, 1);
        for (int i = 1; i < n; i++){
            if (r[i] > r[i-1]) ans[i] = ans[i-1] + 1;
        }
        for (int i = n-2; i > -1; i--){
            if (r[i] > r[i+1] && ans[i] <= ans[i+1]) ans[i] = ans[i+1] + 1;
        }
        return accumulate(ans.begin(), ans.end(), 0);
    }
};