LeetCode 面试经典 150_数组/字符串_分发糖果（15_135_C++_困难）
题目描述：
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 * 109
0 <= ratings[i] <= 2 * 109
题解：
解题思路：
思路一（贪心算法）：
1、左右代表相邻的两个元素(只考虑两个相邻元素)
->->->->->->->
左 > 右 ；右=1
左 < 右 ；右=左+1
左 = 右 ；右=1
<-<-<-<-<-<-<-
左 > 右 ；左=右+1
左 < 右 ；左=1
左 = 右 ；左=1
① 从 左->右 扫描时，先将每个孩子的糖果置为 1，如果相邻元素中右侧的元素比左侧大，则右侧元素的糖果数等于左侧糖果数+1。
② 从 右->左 扫描时，先将每个孩子的糖果置为 1，如果相邻元素中左侧的元素比右侧大，则左侧元素的糖果数等于右侧糖果数+1。
③ 再挑选出 左->右 和 右->左中较大的元素。
例：ratings = [1,0,2]，left 代表从左到右，right 代表从右到左。
left = [1,1,2]
right= [2,1,1]
ans = 2+1+2=5
2、复杂度分析：
① 时间复杂度：O(n)，n 代表数组的长度，遍历三遍数组。
② 空间复杂度：O(n)，n 代表数组的长度，使用 left 存储从左向右的糖果，使用 right 存储从右向左的糖果。
代码实现
代码实现（思路一（贪心算法））：
class Solution1 {
public:
// 主函数，返回给定评分数组所需的糖果总数
int candy(vector<int>& ratings) {
int count = ratings.size(); // 获取评分数组的长度
vector<int> left(count, 1); // 初始化一个长度为count的数组left，表示每个孩子至少有1颗糖
// 从左到右遍历评分数组，计算每个孩子的糖果数（如果比前一个孩子的评分高，糖果数加1）
for (int i = 1; i < count; i++) {
if (ratings[i] > ratings[i - 1]) { // 如果当前孩子的评分高于前一个孩子
left[i] = left[i - 1] + 1; // 当前孩子的糖果数比前一个孩子多1
}
}
vector<int> right(count, 1); // 初始化一个长度为count的数组right，表示每个孩子至少有1颗糖
// 从右到左遍历评分数组，计算每个孩子的糖果数（如果比下一个孩子的评分高，糖果数加1）
for (int i = count - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) { // 如果当前孩子的评分高于下一个孩子
right[i] = right[i + 1] + 1; // 当前孩子的糖果数比下一个孩子多1
}
}
int ans = 0; // 用于存储总糖果数
// 遍历所有孩子，取每个孩子在left和right数组中的最大值（这保证了当前孩子能够得到最大可能的糖果数）
for (int i = 0; i < count; i++) {
ans += max(left[i], right[i]); // 取最大值，避免重复计算
}
return ans; // 返回总糖果数
}
};
代码实现（对思路一代码进行优化）：
/** 优化存储空间（只使用一个额外的数组）
* 只使用一个额外的数组存储 左->右 扫描的结果
* 从 右->左 扫描时，边计算 右->左 的糖果数量，边计算ans（总糖果数）
* 时间复杂度：O(n),遍历了两遍数组。
* 空间复杂度：O(n),使用了一个额外的数组空间。
*/
class Solution2 {
public:
// 主函数，返回给定评分数组所需的糖果总数
int candy(vector<int>& ratings) {
int count = ratings.size(); // 获取评分数组的长度
vector<int> left(count, 1); // 初始化一个长度为count的数组left，表示每个孩子至少有1颗糖
// 从左到右遍历评分数组，计算每个孩子的糖果数（如果比前一个孩子的评分高，糖果数加1）
for (int i = 1; i < count; i++) {
if (ratings[i] > ratings[i - 1]) { // 如果当前孩子的评分高于前一个孩子
left[i] = left[i - 1] + 1; // 当前孩子的糖果数比前一个孩子多1
}
}
// 初始化右边的糖果数，先假设最后一个孩子右边没有其他孩子
int ans = left[count-1]; // 初始总糖果数为最后一个孩子的糖果数
int right = 1; // 右侧的临时糖果数，初始化为1，因为每个孩子至少有1颗糖
// 从右到左遍历评分数组，计算每个孩子的糖果数（如果比下一个孩子的评分高，糖果数加1）
for (int i = count - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) { // 如果当前孩子的评分高于下一个孩子
right = right + 1; // 当前孩子的糖果数增加
} else {
right = 1; // 如果当前孩子的评分不高于下一个孩子，糖果数恢复为1
}
// 更新总糖果数：取左边和右边糖果数的最大值
// left[i]是从左到右计算的糖果数，right是从右到左计算的糖果数
ans += max(right, left[i]); // 累加当前孩子的最大糖果数
}
return ans; // 返回总糖果数
}
};
以思路一为例进行调试
#include<iostream>
#include<vector>
using namespace std;
class Solution1 {
public:
// 主函数，返回给定评分数组所需的糖果总数
int candy(vector<int>& ratings) {
int count = ratings.size(); // 获取评分数组的长度
vector<int> left(count, 1); // 初始化一个长度为count的数组left，表示每个孩子至少有1颗糖
// 从左到右遍历评分数组，计算每个孩子的糖果数（如果比前一个孩子的评分高，糖果数加1）
for (int i = 1; i < count; i++) {
if (ratings[i] > ratings[i - 1]) { // 如果当前孩子的评分高于前一个孩子
left[i] = left[i - 1] + 1; // 当前孩子的糖果数比前一个孩子多1
}
}
// 初始化右边的糖果数，先假设最后一个孩子右边没有其他孩子
int ans = left[count-1]; // 初始总糖果数为最后一个孩子的糖果数
int right = 1; // 右侧的临时糖果数，初始化为1，因为每个孩子至少有1颗糖
// 从右到左遍历评分数组，计算每个孩子的糖果数（如果比下一个孩子的评分高，糖果数加1）
for (int i = count - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) { // 如果当前孩子的评分高于下一个孩子
right = right + 1; // 当前孩子的糖果数增加
} else {
right = 1; // 如果当前孩子的评分不高于下一个孩子，糖果数恢复为1
}
// 更新总糖果数：取左边和右边糖果数的最大值
// left[i]是从左到右计算的糖果数，right是从右到左计算的糖果数
ans += max(right, left[i]); // 累加当前孩子的最大糖果数
}
return ans; // 返回总糖果数
}
};
int main(int argc, char const *argv[])
{
vector<int> ratings = {1,0,2};
Solution1 s;
cout<<s.candy(ratings);
return 0;
}
LeetCode 面试经典 150_数组/字符串_分发糖果（15_135)原题链接
欢迎大家和我沟通交流(✿◠‿◠)