n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。 相邻两个孩子中，评分更高的那个会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
codeType
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
codeType
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
codeType
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
解法：
这题可以用贪心算法解答，只要遍历两边，分别得到满足左规则和右规则的两个数组即可。最终该解法的时间复杂度为O(n)，空间复杂度也为O(n)。
- 左规则：当 ratings[i−1]<ratings[i] 时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。
- 右规则：当 ratings[i]>ratings[i+1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多。
typescript
function candy(ratings: number[]): number {
// 这题可以用贪心法求解，只要分别得到满足左规则和右规则的两个数组，同一个位置i取max(L[i], R[i])即可
const n: number = ratings.length
const L: number[] = new Array(n).fill(1)
const R: number[] = new Array(n).fill(1)
L[0] = 1 // 最左边的孩子左边没人，所以初始化为1，其实可以省了
for(let i=1; i < n; i++){ // 先得到满足左规则的数组
if(ratings[i] > ratings[i-1]){
L[i] = L[i-1] + 1 // 如果大于左边孩子的评分，那么就比他多一个
}else{
L[i] = 1 // 如果小于左边孩子的评分，那么就从0开始，这里也可以省略
}
}
R[n-1] = 1 // 最右边的孩子右边没人所以初始化为1
for(let i=n-2; i>=0; i--){ // 得到满足右边的数组，这里其实可以不用申请R[i],运行时直接计算结果就行，这样写直观一点。
if(ratings[i] > ratings[i+1]){
R[i] = R[i+1] + 1 // 比右边孩子评分高，比右边孩子多一个糖
}else{
R[i] = 1
}
}
let sum: number = 0
for(let i=0; i<n; i++){
sum += Math.max(L[i], R[i]) // 取两者间大的一个，也就是同时可以满足左右规则的数量
}
return sum
};