AlgoPressAppearance
0135-分发糖果
https://leetcode.cn/problems/candy/
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
- n == ratings.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
思路:设置 up/down 累计需要增加的糖果数
相同的时候计算错误 第一个孩子先分配1颗糖，当第二个孩子比他分值低的时候，前一个孩子加1颗糖。 后面每次递增就增加1颗糖，否则就降为1颗 堆栈的太复杂了
参考代码
csharp
public class Solution {
public int Candy(int[] ratings) {
int up = 0;
int down = 0;
int sum = 1;
string pre = "up";
for(int i=1; i < ratings.Length; i++){
if(ratings[i] < ratings[i-1] || ratings[i] == ratings[i-1] && pre == "up"){
up = 0;
down++;
sum+=down;
pre="down";
}
else if(ratings[i] > ratings[i-1] || ratings[i] == ratings[i-1] && pre == "down"){
down=-1;
up++;
sum+=up;
pre="up";
}
sum+=1;
}
return sum;
}
}
csharp
public class Solution{
public int Candy(int[] ratings){
int n = ratings.Length;
int sum = 1;
int inc = 1; //递增序列长度
int dec = 0; //递减序列长度
int pre = 1; //前一个同学分配的个数
for(int i=1; i<n; i++){
if(ratings[i] >= ratings[i-1]){
dec = 0;
pre = ratings[i] == ratings[i-1] ? 1 : pre+1;
sum += pre;
inc = pre;
}
else{
dec++;
if(dec == inc){
dec++;
}
sum+= dec;
pre = 1;
}
}
return sum;
}
}
思路2：从左往右，从右往左
先从左往右，当发现 rating[i] > rating[i-1] 的时候，就将糖果加1，否则设置为1 然后从右往左，计算当 rating[i] > rating[i+1] 的时候，糖果必须大于前面的那个数，否则保持当前的那个数
csharp
public class Solution{
public int Candy(int[] ratings){
int n = ratings.Length;
int[] left = new int[n];
//从左往右
for(int i=1; i<n; i++){
if(i>0 && ratings[i] > ratings[i-1]){
left[i] = left[i-1]+1;
}
else{
left[i] = 1;
}
}
//从右往左
int right=0, sum = 0;
for(int i=n-1; i>=0; i--){
if(i < n-1 && ratings[i] > ratings[i+1]){
right++;
}
else{
right = 1;
}
sum+=Math.Max(left[i],right);
}
return sum;
}
}
复习：从左往右从右往左 20220514
csharp
public class Solution {
public int Candy(int[] ratings) {
int n = ratings.Length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = 1;
for(int i=1;i<n;i++){
left[i] = ratings[i] > ratings[i-1] ? left[i-1]+1 : 1;
}
right[n-1] = 1;
for(int i=n-2;i>=0;i--){
right[i] = ratings[i] > ratings[i+1] ? right[i+1]+1 : 1;
}
int count = 0;
for(int i=0;i<n;i++){
count += Math.Max(left[i],right[i]);
}
return count;
}
}
复习：迭代法
主要处理两个， 1 : 相等的情况 2 : 下降序列和递增序列相同的情况，需要将 dec++
csharp
public class Solution {
public int Candy(int[] ratings) {
//直接计算
//设置 pre 为前一个分配的数量，当递增的时候，pre 依次加1
//当开始递减的时候，记录递减序列，分配1颗糖
//这里有两个问题要注意， 1. 当递减序为第二个的时候，我们需要为前面已经递减的增加糖果数，所以需要记录递减序列个数
//2. 当递减序列个数，和前面递增序列个数相等的时候，需要多增加一个糖
//注意糖果相等时候：按照升序处理，当和前一个相等的时候，设置为1
int pre = 1; //前一个分配的糖果数
int inc = 1; //递增序列个数
int dec = 0; //递减序列个数
int count = 1; //糖果数,第一个分配为1
for(int i=1; i<ratings.Length; i++){
if(ratings[i] >= ratings[i-1]){
dec = 0;
pre = ratings[i] > ratings[i-1] ? pre + 1 : 1;
count += pre;
inc = pre;
}
else{
dec++;
if(dec == inc){ //比如前面就是一个1，测试开始递增，所以当前分配一个糖的时候，前面还需要补一颗
dec++;
}
count += dec;
pre = 1;
}
}
return count;
}
}
可以将初始值统计设置为1
csharp
public class Solution {
public int Candy(int[] ratings) {
//直接计算
//设置 pre 为前一个分配的数量，当递增的时候，pre 依次加1
//当开始递减的时候，记录递减序列，分配1颗糖
//这里有两个问题要注意， 1. 当递减序为第二个的时候，我们需要为前面已经递减的增加糖果数，所以需要记录递减序列个数
//2. 当递减序列个数，和前面递增序列个数相等的时候，需要多增加一个糖
//注意糖果相等时候：按照升序处理，当和前一个相等的时候，设置为1
int pre = 1; //前一个分配的糖果数
int inc = 1; //递增序列个数
int dec = 1; //递减序列个数
int count = 1; //糖果数,第一个分配为1
for(int i=1; i<ratings.Length; i++){
if(ratings[i] >= ratings[i-1]){
dec = 1;
pre = ratings[i] > ratings[i-1] ? pre + 1 : 1;
count += pre;
inc = pre;
}
else{
if(dec == inc){ //比如前面就是一个1，测试开始递增，所以当前分配一个糖的时候，前面还需要补一颗
dec++;
}
count += dec;
pre = 1;
dec++;
}
}
return count;
}
}