代码随想录算法训练营第三十四天|LeetCode135 分发糖果

题1：

指路：135. 分发糖果 - 力扣（LeetCode）

思路与代码：

这个题我们需要分开情况考虑：右边的分数大于左边，这时候右边对应的糖果数量就要在左边的基础上加一；相似的，再考虑左边的分数大于右边，这时候需要从后往前遍历，此时左边对应的数量就要在右边的基础上加一。如此，我们会在一个孩子的对应糖果值上得到两个值，选取较大值可以满足这两个条件。最后将得到的糖果数量累加即可。代码如下：

class Solution {
public:
    int candy(vector<int>& ratings) {
    int ans = 0;
    int n = ratings.size();
    vector<int>candy (n, 1);  // n个1初始化糖果
    for (int i = 1; i < ratings.size(); i++) { 
        if (ratings[i] > ratings[i - 1]) {  // 右边大于左边
            candy[i] = candy[i - 1] + 1;
        }
    }
    for (int i = ratings.size() - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {  // 左边大于右边
            candy[i] = max(candy[i], candy[i + 1] + 1);
        }
    }
    for (int i = 0; i < candy.size(); i++) {
        ans += candy[i];
    }
    return ans;
    }
};