题目描述

原题链接：135. 分发糖果

解题思路

因为本题的值与左右两侧都有关系，若一趟遍历一起考虑的话，很复杂。因此，分情况来遍历。
（1）左值小于右值
局部最优解： 右值比左值多一个。
全局最优解： 相邻孩子，评分高的右值比左值大。

（2）左值大于等于右值
局部最优解： 1）某个数比右侧值大，比左侧值小，则该值比右侧值多一个；2）某个数比右侧值大，比左侧值也大，则该值取比右侧多一个与比左侧值多一个之间的最大值。
全局最优解： 相邻孩子，评分高的左值比右值大，并且评分高的右值也比左值大。

对于2)中情况，若出现[1,3,4,5,2]，此时在5这个位置上，它即比它的左值大，也比它的右值，若还按照右值加一的，那么会让5对应的糖果数变为2，就会比4对应的糖果树小，因此取右侧多一个与比左侧值多一个之间的最大值。

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 左 < 右
        for(int i = 1; i < ratings.size(); i++) {
            if(ratings[i - 1] < ratings[i])     candyVec[i] = candyVec[i - 1] + 1;
        }
        // 左 > 右
        for(int i = ratings.size() - 2; i >= 0; i--) {
            // 当找到一个数即比左边大，右比右边大的话，取右边加一与左边值之间的最大值
            if(ratings[i] > ratings[i + 1])     candyVec[i] = max(candyVec[i + 1] + 1, candyVec[i]);
        }
        int res = 0;
        for(int i = 0; i < candyVec.size(); i++)        res += candyVec[i];
        return res;
    }
};

参考文章：135. 分发糖果