題目描述：

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)原題鏈接
歡迎大家和我溝通交流(????)