135. 分发糖果
常数空间的那个方法我没看懂
使用贪心算法
根据题目要求，相邻两个孩子评分更高的孩子会获得更多的糖果
也就相当于左规则要求这个孩子比他左边的孩子获得更多糖果，右规则要求这个孩子比他右边的孩子获得更多糖果，在做有规则均满足时，符合要求。
于是
从左到右遍历，右大于左，则右多分发一个糖果，完成左规则，反向完成右规则。
最后遍历，每个孩子取左右规则下最大糖果数。
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> left(n, 0);
vector<int> right(n, 0);
for (int i = 1; i < n; ++i) {
if (ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; --i) {
if (ratings[i] > ratings[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
int sum = n;
for (int i = 0; i < n; ++i) {
sum += max(left[i], right[i]);
}
return sum;
}
};