一、题目描述

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 * 104
• 0 <= ratings[i] <= 2 * 104

二、题目分析

虽然标注是个困难题，但是也别被吓到，直接看题，主要就是根据递增或者递减序列的长度给予糖果，不过需要确定递增递减的糖果分配规则：

如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 pre+1 个糖果即可。否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。

特殊情况：

假设有一段递增序列，紧接着是一段递减序列。例如，评分为 [1, 2, 3, 2, 1]：

1. 从左到右遍历后，糖果分配为 [1, 2, 3, 1, 1]。
2. 从右到左遍历后，糖果分配为 [1, 2, 3, 2, 1]。

在这个例子中，递减序列的长度为 2（评分 [3, 2, 1] 中递减部分为 [2, 1]），而之前的递增序列的长度为 2（评分 [1, 2, 3] 中递增部分为 [1, 2, 3]）。此时，递减序列的长度等于递增序列的长度。

问题出现：

如果递减序列的长度等于递增序列的长度，那么递增序列的最后一个孩子（评分最高的孩子）的糖果数可能不足以满足递减序列的需求。例如：

• 递增序列 [1, 2, 3] 分配糖果 [1, 2, 3]。
• 递减序列 [3, 2, 1] 需要分配糖果 [3, 2, 1]。

如果直接将递减序列的糖果数分配为 [2, 1]，那么递增序列的最后一个孩子（评分为 3）的糖果数为 3，而递减序列的第一个孩子（评分为 2）的糖果数为 2，这没有问题。但是，如果递减序列的长度等于递增序列的长度，可能会导致递增序列的最后一个孩子的糖果数不足。

三、代码实现

通过一次遍历来解决问题，主要逻辑如下：

1. 初始化：
   • sum 表示总糖果数，初始值为 1（第一个孩子至少分到 1 颗糖果）。
   • leng 和 fleng 用于记录当前递增和递减的长度。
   • tang 表示当前孩子分到的糖果数。
2. 遍历数组：
   • 如果当前孩子的评分大于或等于前一个孩子：
     • 如果评分相等，当前孩子分到 1 颗糖果。
     • 如果评分更高，当前孩子分到的糖果数比前一个孩子多 1。
     • 更新 sum 和 leng。
   • 如果当前孩子的评分小于前一个孩子：
     • 增加递减长度 fleng。
     • 如果递减长度等于之前的递增长度 leng，则 fleng 需要加 1。
     • 更新 sum 和重置 tang。
3. 返回结果：
   • 最终返回 sum，即总糖果数。

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
	    	int sum = 1;
	    	int leng = 1,fleng = 0,tang = 1;
	    	for(int i=1;i<n;i++) {
	    		if(ratings[i] >= ratings[i-1]) {
	    			fleng = 0;
	    			if(ratings[i] == ratings[i-1]) {
	    				tang = 1;
	    			}
	    			else tang++;
	    			sum+=tang;
	    			leng = tang;
	    		}
	    		else {
	    			fleng++;
	    			if(fleng == leng) {
	    				fleng ++;
	    			}
	    			sum+=fleng;
	    			tang = 1;
	    		}
	    	}
	    	return sum;
    }
}

四、总结

有时候一些特殊情况是在跑的时候才发现的，所以遇到困难并不可怕，在整理完思路和条件后，其实这道困难题也没有多困难。