思路

這道題目一定是要確定一邊之后，再確定另一邊，例如比較每一個孩子的左邊，然后再比較右邊，「如果兩邊一起考慮一定會顧此失彼」。

先確定右邊評分大于左邊的情況（也就是從前向后遍歷）

此時局部最優：只要右邊評分比左邊大，右邊的孩子就多一個糖果，全局最優：相鄰的孩子中，評分高的右孩子獲得比左邊孩子更多的糖果

局部最優可以推出全局最優。

如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一個，所以貪心：candyVec[i] = candyVec[i - 1] + 1。

再確定左孩子大于右孩子的情況（從后向前遍歷）

為什么不能從前向后遍歷呢？

因為如果從前向后遍歷，根據 ratings[i + 1] 來確定 ratings[i] 對應的糖果，那么每次都不能利用上前一次的比較結果了。會出現評分高的孩子和評分低的孩子糖果數相同的情況。

[1,2,87,87,87,2,1]

1 2 3 1 1 1 1 10
1 2 3 1 2 2 1 12
1 2 3 1 3 2 1 13

「所以確定左孩子大于右孩子的情況一定要從后向前遍歷！」

如果 ratings[i] > ratings[i + 1]，此時candyVec[i]（第i個小孩的糖果數量）就有兩個選擇了，一個是candyVec[i + 1] + 1（從右邊這個加1得到的糖果數量），一個是candyVec[i]（之前比較右孩子大于左孩子得到的糖果數量）。

那么又要貪心了，局部最優：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果數量，保證第i個小孩的糖果數量既大于左邊的也大于右邊的。全局最優：相鄰的孩子中，評分高的孩子獲得更多的糖果。

局部最優可以推出全局最優。

所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果數量，「candyVec[i]只有取最大的才能既保證比左邊candyVec[i - 1]的糖果多，也比右邊candyVec[i + 1]的糖果多」。

評分更高的孩子必須比他兩側的鄰位孩子獲得更多的糖果。
(意思是評分高的孩子糖果越多，假如123，這種情況，孩子1一顆糖果，孩子2就有2顆，孩子3就有3顆，因為要保證評分高的孩子比鄰位孩子糖果數多。)

那么這樣下來，老師至少需要準備多少顆糖果呢？說明評分高的孩子獲得的糖果不能累加，如010 這種情況，中間的孩子比左右兩個孩子評分都高，但也只能比他們多獲得一顆糖果。

在比如221這中情況，比較左孩子的時候哪個孩子都沒有多得糖果，比較右孩子的時候，中間孩子多獲得了一顆糖果，這兩個例子說明比較左孩子的時候可能獲得了糖果也可能沒有獲得糖果。所以有兩個選擇。
第一個選擇是如果當前孩子在比較左孩子的時候獲得了獎勵糖果，并且現在比右孩子評分高，那么它的糖果就要保持自己原來所有，不能累加。
第二個選擇：如果當前孩子在比較左孩子的時候沒有獲得獎勵，并且現在比右孩子評分高，那么它的糖果就要比右孩子多一顆。
所以兩者選最大的。

class Solution { public:int candy(vector<int>& ratings) {vector<int> candies(ratings.size(),1);for(int ii=1;ii<ratings.size();ii++){if(ratings[ii]>ratings[ii-1]) candies[ii]=candies[ii-1]+1;}for(int ii=ratings.size()-2;ii>=0;ii--){if(ratings[ii]>ratings[ii+1]) candies[ii]=max(candies[ii+1]+1,candies[ii]);}int res=0;for(auto a : candies){res+=a;}return res;} };

總結

本題的兩次貪心的策略：

一次是從左到右遍歷，只比較右邊孩子評分比左邊大的情況。
一次是從右到左遍歷，只比較左邊孩子評分比右邊大的情況。
這樣從局部最優推出了全局最優，即：相鄰的孩子中，評分高的孩子獲得更多的糖果。

總結

以上是生活随笔為你收集整理的分发糖果！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。