贪心
时间复杂度O(n) 空间复杂度O(n)
class Solution {
public:
int candy(vector<int>& ratings) {
if(ratings.size() == 1) return 1;
//c[]记录每个孩子分发糖果数
vector<int> c(ratings.size(), 1);
//从左往右:若后者评分更高,则理应后者比前者糖果至少多一个
for(int i = 1; i < ratings.size(); i++) {
if(ratings[i] > ratings[i-1]) c[i] = c[i-1]+1;
}
//从右向左:若前者比后者评分更高,则前者理应比后者至少多一个糖果,
//并取max
for(int i = ratings.size()-2; i >= 0; i--) {
if(ratings[i] > ratings[i+1]) c[i] = max(c[i+1]+1, c[i]);
}
int res = 0;
for(int i = 0; i < ratings.size(); i++) res += c[i];
return res;
}
};