题目描述:
老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。
你需要按照以下要求,帮助老师给这些孩子分发糖果:
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中,评分高的孩子必须获得更多的糖果。
那么这样下来,老师至少需要准备多少颗糖果呢?
分析:
分析一下,乍一看好像这个小朋友的糖果之和他旁边的小朋友有关,但是思考一下好像也不大对,旁边的小朋友又会受旁边的旁边影响。
我们把能想到的情况列出来:
- 左边的小朋友分数 < 当前小朋友分数, 当前小朋友分数 = 左边的小朋友分数 + 1
- 左边的小朋友分数 > 当前小朋友分数, 当前小朋友分数=1, 左边如果呈递减的趋势,那么递减的序列对应加1(还有特殊情况)
- 峰值的点的取值很重要
- 比如1 5 4, 4位当前节点,5为峰值,设置为1,前面5不需要(5已经加过了【不包含峰值】)
- 比如1 5 4 3 2, 2位当前节点,5为峰值,设置为1,前面5 4 3全部加一
- 比如1 2 3 5 4 3 2 1, 1位当前节点,5为峰值,设置为1,前面4 3 2全部加一(5需要设置为两边最高值加一)
- 比如1 4 4 3 2, 2位当前节点,5为峰值,设置为1,前面4 3全部加一(峰值指向后面那个4【包含峰值】)
代码:
class Solution {
public:
int candy(vector<int>& ratings) {
//每个小宝贝至少有一颗糖,相邻小伙伴分数高要获得更多的糖果
//记录峰值,比如1 5 4 3 2,topIndex指向5
//记录峰值,比如1 4 4 3 2,topIndex指向第二个4
int topIndex = 0;
//记录峰值下标对应小宝贝的糖果数
int topIndexValue = 1;
int len = ratings.size();
//下界
if(len == 0) return 0;
//长度不等于0,那么第一个小朋友初始肯定设置为1
int result = 1;
//记录左侧小朋友多少颗糖,最开始那个是1颗糖
int leftValue = 1;
for(int i = 1; i < len; i++){
//和左侧判断
if(ratings[i] >= ratings[i-1]) {
if(ratings[i] > ratings[i-1]){
result += (leftValue + 1);
//刷新
leftValue = leftValue + 1;
}
else{
result += 1; //等于情况
leftValue = 1;
}
//刷新峰值
topIndex = i;
topIndexValue = leftValue;
}else{
//左边的小朋友分数 > 当前小朋友分数, 当前小朋友分数=1, 左边如果呈递减的趋势,那么递减的序列对应加1
//峰值的点的取值很重要
//比如1 5 4, 4位当前节点,设置为1,前面5不需要(5已经加过了【不包含峰值】)
//比如1 5 4 3 2, 2位当前节点,设置为1,前面5 4 3全部加一
//比如1 2 3 5 4 3 2 1, 1位当前节点,设置为1,前面4 3 2全部加一(5需要设置为两边最高值加一)
//比如1 4 4 3 2, 2位当前节点,设置为1,前面4 3全部加一(峰值指向后面那个4【包含峰值】)
//判断峰值和前一个对等还是大于
if(topIndex > 0){
if(ratings[topIndex] == ratings[topIndex-1]) result += (i - topIndex + 1);
else {
//山峰形状
//首先除了峰值那个点全部+1
result += (i - (topIndex + 1) + 1);
//然后对峰值点判断
result = topIndexValue >= (1 + i - topIndex) ? result : result + (1 + i - topIndex - topIndexValue);
//更新峰值
topIndexValue = max(topIndexValue, (1 + i - topIndex));
}
}
else result += (i - topIndex + 1); //峰值为第一个,左边没有
//刷新
leftValue = 1;
}
}
return result;
}
};