网站建设需要待摊吗,辽宁建设工程信息网为什么上不去啦,重庆高端网站制作,曲阜人网站n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求#xff0c;给这些孩子分发糖果#xff1a;
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果#xff0c;计算并返回需要准备的…
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
int candy(vectorint ratings) {int mintratings[0];int nratings.size(); for(int i0;in;i){mintmin(ratings[i],mint);}vectorintans(n,0); //情况一最小值和凹点的评分都为1for(int i0;in;i){if(ratings[i]mint) //最小值ans[i]1;if(i0(in-1)ratings[i]ratings[i-1]ratings[i]ratings[i1]) //凹点ans[i]1;}ans[n-1]1;ans[0]1;//情况二这样/的斜坡后一个孩子比前一个大1for(int i1;in;i){if(ratings[i]ratings[i-1])ans[i]max(ans[i-1]1,ans[i]);elsecontinue;}//情况三这样\的斜坡前一个比后一个大1for(int in-2;i0;i--){if(ratings[i]ratings[i1]){ans[i]max(ans[i1]1,ans[i]); //遇到和/斜坡公共的凸点取两者最大值}elsecontinue;}int sum0;for(int i0;in;i){sumans[i];}return sum;
}
妙啊又名资本家发工资算法
首先要发最少设置在发工资和第一个最小之间取最小值
若没有凹点也就是周围都一样评分那么众生平等
若后面的大于前面的则后加1反之前加1
更新每一个人发的最后将各个局部最小值求和
