一、题目描述
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
二、测试用例
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
三、解题思路
- 基本思路：
对于每个孩子来说，他获得的糖果数取决于它的邻居，那就可以分解为两种情况，一种是相对于左邻居来确定他的糖果数，另一种是相对于右邻居来确定他的糖果数，这两种情况要同时满足，则要取两种情况最大的糖果数。【反证法：如果取小的那个，他只能满足一种情况，例如：相对于左邻居，他应该是 4 颗，相对于右邻居，他应该是 5 颗，如果我们取 4 颗，他就无法满足右邻居的情况】 - 具体思路：
- 定义相对左右邻居糖果数序列 L 和 R，初始化都为 1 ；定义总糖果数 sum ，初始化为 0 ；
- 计算左邻居序列：从头到尾，对于第 i 个小朋友来说，如果他比他的左邻居大，那他的糖果数就要比他的左邻居多 1 颗；否则，那他就只有最低的 1 颗糖果。【只有 1 颗糖果才能保证他一定比他的左邻居小，因为每个小朋友最少获得 1 颗】
- 计算右邻居序列：从尾到头，对于第 i 个小朋友来说，如果他比他的右邻居大，那他的糖果数就要比他的右邻居多 1 颗，否则，那他就只有最低的 1 颗糖果。
- 计算总糖果数：累加每个小朋友的糖果数，对于第 i 个小朋友来说，他的糖果数要取
L[i]和R[i]最大的一个。【解释：对于每个小朋友来说，他与邻居的关系就四种情况，分别是L<M<R ，L<M>R ，L>M<R ，L>M>R。- ①
L<M<R：M 的相对左邻居糖果数就是 L+1，相对右邻居糖果数就是 1 ，则 M 的糖果数为 L+1；（满足 L<M ，也满足 M<R ，因为对于 R 来说，他的相对左邻居糖果数是 M+1=L+1+1，相对右邻居不知道，但是取相对左右邻居的最大，所以他的糖果数一定大于等于左邻居糖果数 L+2 。） - ②
L<M>R：M 相对 L 和 R 是最大值，最大的最大，肯定是最大，肯定满足 L<M 和 M>R ； - ③
L>M<R：M 相对 L 和 R 是最小值，M 的相对左右邻居糖果数都是 1，所以 M 的糖果数是 1 。【每个小朋友最少分的 1 颗糖果】 - ④
L>M>R：第一种情况的方向
】
- ①
四、参考代码
时间复杂度：
O
(
n
)
\Omicron(n)
O(n)
空间复杂度：
O
(
n
)
\Omicron(n)
O(n)
class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
vector<int> L(n,1),R(n,1);
int sum=0;
for(int i=1;i<n;i++){
if(ratings[i]>ratings[i-1]){
L[i]=L[i-1]+1;
}
if(ratings[n-i-1]>ratings[n-i]){
R[n-i-1]=R[n-i]+1;
}
}
for(int i=0;i<n;i++){
sum+=max(L[i],R[i]);
}
return sum;
}
};