link: 135.分发糖果
题目描述
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
思路历程
咋一看，好像挺简单的.但是细细想来好像不是那么简单。
- 首先找到评分最低的孩子，他只能获得 1 个糖果，
- 相邻他的孩子能够获取 2 个糖果。
- 这个结论好像也不是必须的。和评分最低相邻的孩子获得的糖果数不一定是 2 个
- 如下图，评分 5 的孩子会获得 3 个糖果.
- 那么首先要确定哪些孩子会分到一个糖果
- 很显然，位于 “波底” – 即 两侧评分都大于自身的孩子的评分 会一定被分配一个糖果.
- 还有一个关键点：连续相等的评分的情况该如何考虑
show code
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
if(n == 1) {
return 1;
}
// 对应保存分配的糖果数.
int[] allocation = new int[n];
for(int i = 0;i = ratings[i]) {
// 如果后一个孩子的评分 大于等于 当前孩子的评分，服务器托管网那么则分配一个糖果
allocation[i] = 1;
}
continue;
}
if(i == n - 1) {
// 如果前一个孩子的评分 大于等于 当前孩子的评分，那么则分配一个糖果
if(ratings[i - 1] >= ratings[i]) {
allocation[i] = 1;
}
}
// 如果 当前孩子 评分 不大于相邻孩子，那么 分配一个糖果
if(i = i;j--) {
allocation[j] = init++;
}
continue;
}
// 这个时候如果没有被分配糖果有两种情况，一定大于等于左侧孩子评分.
if(i ratings[i + 1]) {
// 向右寻找递减序列
int start = i + 1;
while(start = i;j--) {
allocation[j] = init++;
}
// 对 i 位置分发的糖果进行校验
// 判断是否满足题目条件.
服务器托管网 if(ratings[i] > ratings[i - 1]) {
allocation[i] = Math.max(allocation[i + 1], allocation[i - 1]) + 1;
}
if(ratings[i] == ratings[i - 1]) {
if(ratings[i] > allocation[i + 1]) {
allocation[i] = allocation[i + 1] + 1;
} else {
allocation[i] = allocation[i - 1];
}
}
continue;
}
}
if(i == n - 1) {
allocation[i] = allocation[i - 1] + 1;
}
}
return Arrays.stream(allocation).sum();
}
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: C#里Bitmap转Halocn的HObject
一般情况下，图像的width是4的倍数的话，用以下代码便可将彩色bitmap转出halcon里的HObject public void Bitmap2HObject(Bitmap bmp, out HObject image) { try { Rectangl…
