贪心算法
贪心策略:在每次遍历中,仅考虑并更新相邻一侧的大小关系
class Solution {
public:
int candy(vector<int>& ratings) {
int size = ratings.size();
if(size<2){
return size;
}
vector<int> num(size,1);
//从左到右
for(int i=0;i<size-1;i++){
if(ratings[i+1]>ratings[i])
num[i+1] = num[i] + 1;
}
//从右到左
for(int i=size-1;i>0;i--){
if(ratings[i]<ratings[i-1])
num[i-1] = max(num[i] + 1,num[i-1]);
}
return accumulate(num.begin(),num.end(),0);
}
};
标签:ratings,int,Candy,num,135,LeetCode,size
From: https://www.cnblogs.com/poteitoutou/p/16870837.html