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

题解：

解题思路：

思路一（贪心算法）：

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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)