题目：
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
题目示例：
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
解题方法1：
双向遍历
代码：
class Solution:
def candy(self, ratings: List[int]) -> int:
num=[0]*len(ratings) #用来保存遍历每个位置的糖果数目
num[0]=1 #正向第一位为1
for i in range(1,len(ratings)):
if ratings[i]>ratings[i-1]: #大于则前置加1赋予
num[i]=num[i-1]+1
else:
num[i]=1 #否则置1
result=0 #最终分发糖果数目
result=result+max(1,num[len(ratings)-1]) #先将反向第一位置于结果
right=1 #反向第一位为1
for i in range(len(ratings)-2,-1,-1):
if ratings[i]>ratings[i+1]: #反向赋予大于前置加1
right+=1
else:
right=1 #否则置0
result=result+max(right,num[i]) #正向反向对比，赋予结果里
return result代码思路：
这道题的思路就是要保证得分大的要比得分小的得到的糖果多。
先不考虑边界，一个数目有两边大小比较，单次遍历只能看一边。
所以正向遍历，反向遍历两次
第一次正向遍历满足糖果多的比左边大，第二次反向遍历满足糖果多的比右边大
因为要保证左右均满足，所有取正向反向糖果数目最大，相加即最终结果
代码逻辑：
num保存正向遍历结果，right变量保存反向结果，不用数组节省空间
正向遍历如果右边数组比左边大，即前置数目+1，否则置1
反向同，如果左边数组比右边大，则前置数目+1，否则置1
两个对比取最大，最大数即当前位置分发糖果数，将最大数累加到结果里
空间复杂度为O(n),时间复杂度O(n)
解题方法2：
找递增递减规律
代码：
class Solution:
def candy(self, ratings: List[int]) -> int:
dizeng=1 #递增长度
dijian=0 #递减长度
idx=1 #idx记录当前递增糖果数
result=1 #返回结果数
for i in range(1,len(ratings)):
if ratings[i]>ratings[i-1]: #大于递增序列
dijian=0 #递减置0
idx+=1 #递增+1
dizeng=idx #递增长度赋予
result+=idx #结果返回
elif ratings[i]==ratings[i-1]: #等于赋1序列，递增为1
dijian=0
dizeng=1
idx=1
result+=1
else: #递减序列统计
dijian+=1 #递减长度+1
if dijian==dizeng:
dijian+=1 #说明前递增序列最后一位要加入递减序列
result+=dijian #可以看为在递减序列最顶部插入
idx=1
return result代码思路：
可以将得分看作递增序列与递减序列，
时刻记录递增序列长度与递减序列长度
难点在于当递减序列长度与递增长度相同时，递增序列的最后一位也要加入递减序列
代码逻辑：
分为三块，递增统计，不变统计与递减统计
空间复杂度为O(1),时间复杂度O(n)
标签：分发,ratings,递增,result,135,序列,递减,糖果,leetcode From： https://blog.csdn.net/qq_60461973/article/details/140276801