https://leetcode.com/problems/candy/description/
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
字面意思就是一行人分糖果,如果一个人比旁边的人得分多,那么必须也比旁边的人糖果多,问最少需要糖果数量
问题就出在,如果和旁边的人得分一样,那么这个人得多少糖果呢?
这个问题纠结了我好久啊,各种办法都行不通。
举个例子 22输出2 221输出4
整个方向跑偏了
为什么要纠结这个问题呢
只要两个方向都满足题目要求的就好了啊QAQ
根本没有必要还得算基于最优的结果整体平移了多少
题面其实可以理解为:
遇到比当前位置大的,就加一,不要管其他大小比较的
p.s.发现一个好东西vector<int>val(ratings.size(),1);和accumulate(val.begin(),val.end(),0);
class Solution {
public:
int candy(vector<int> &ratings) {
if(ratings.size()<=1) return ratings.size();
vector<int>val(ratings.size(),1);
for(int i=1;i<ratings.size();i++)
if(ratings[i]>ratings[i-1])
val[i]=val[i-1]+1;
for(int i=ratings.size()-2;i>=0;i--)
if(ratings[i]>ratings[i+1]&&val[i]<=val[i+1])
val[i]=val[i+1]+1;
return accumulate(val.begin(),val.end(),0);
}
};