135. Candy 【LeetCode】

问题描述：

题目意思是：要你找出这样的最小值满足：
1.每个小朋友至少发一个糖果
2.每个等级更高的小朋友要比其左右两边的小朋友的糖果多

思路：从左到右遍历，只要右边比左边的等级高，就把糖果在左边的基础上增加一个；
再从右到左遍历，只要左边比右边等级高并且左边的糖果数不大于右边，就把糖果数在右边的基础上加一。

代码如下：

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