文章目錄

• 前言
• 一、題目
• 二、思路詳解
• 三、搞點(diǎn)實(shí)際點(diǎn)兒的（C++實(shí)現(xiàn)）
• • 1.略顯粗糙的代碼實(shí)現(xiàn)
  • 2.稍顯精致的代碼實(shí)現(xiàn)
  • 3.最終的代碼實(shí)現(xiàn)
  • 4.提交結(jié)果
• 總結(jié)

---

前言

??????本文記錄自己在LeetCode上關(guān)于一道算法題的解題過程，這道題花費(fèi)了不少時(shí)間才通過。感覺在自己的這種解題風(fēng)格道路上走遠(yuǎn)了！但是代碼提交的結(jié)果還是比較滿意的。 哈哈，過程比較曲折，下面為大家一一道來：

---

一、題目

??????老師想給孩子們分發(fā)糖果，有 N 個(gè)孩子站成了一條直線，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)，預(yù)先給他們評分。
??????你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：

??????要求1：每個(gè)孩子至少分配到 1 個(gè)糖果。
??????要求2：評分更高的孩子必須比他兩側(cè)的鄰位孩子獲得更多的糖果。

??????那么這樣下來，老師至少需要準(zhǔn)備多少顆糖果呢？

示例1：

輸入：[1,0,2]
輸出：5
解釋：你可以分別給這三個(gè)孩子分發(fā) 2、1、2 顆糖果。

示例2：

輸入：[1,2,2]
輸出：4
解釋：你可以分別給這三個(gè)孩子分發(fā) 1、2、1 顆糖果。第三個(gè)孩子只得到 1 顆糖果，這已滿足上述兩個(gè)條件。

該題所在網(wǎng)址：https://leetcode-cn.com/problems/candy/

二、思路詳解

??????瞧一瞧，看一看，大家品一下這個(gè)老師有多摳門~

??????首先：給每個(gè)孩子至少給一個(gè)糖果，這個(gè)簡單。要求 2 稍微難理解一點(diǎn)，參考下面這個(gè)示例來理解，概括為：如果一個(gè)孩子兩側(cè)，只要存在一個(gè)比他評分低的孩子，那么他的糖果數(shù)就要比這個(gè)低評分孩子的糖果要多。

這里給出一個(gè)示例：所有孩子的評分：{ 1,0,2,3,4,3,2,2 } 它對應(yīng)的糖果數(shù)：{ 2,1,2,3,4,2,1,1 }。后面會(huì)對這個(gè)示例進(jìn)一步分析。

??????最開始的思路是這樣的：按照平移的思想來設(shè)計(jì)，即；給起始第一個(gè)孩子1顆糖果，依次往后判斷，如果比它大則糖果加1，比它小則減1，碰到相等的情況則另做分析。 最后將整體結(jié)果往上平移（可能有負(fù)數(shù)存在），使得最小糖果數(shù)為1即可。 但是后來發(fā)現(xiàn)不可行，邏輯判斷太復(fù)雜，很難分析。 還有最重要的一點(diǎn)是，糖果數(shù)有時(shí)候會(huì)有一個(gè)突然的下降，比如給出的示例中評分為4和3的孩子，前者給4顆糖果，后者給2顆糖果。

??????所以單純的只從左到右的分析是不充分的，當(dāng)然可以在這個(gè)基礎(chǔ)上再改改，比如補(bǔ)充上從右到左進(jìn)行分析，不過在這兒不聊這個(gè)。聊點(diǎn)清新脫俗的~

————————————————??????華麗麗的分割線

??????就糖果數(shù)突然有一個(gè)下降的現(xiàn)象，我思考了一下原因。從而得到一種解題思路：

??????發(fā)現(xiàn)：如果能找到那些極小值點(diǎn)，也就是那些最終只分配 1 顆糖果的孩子（好慘！），因?yàn)榻o這些孩子的糖果數(shù)是已經(jīng)確定的了。以此（這些糖果數(shù)）為基礎(chǔ)，再對這些孩子的左右分別進(jìn)行分析，很容易就可以確定他們的左右孩子應(yīng)得的糖果數(shù)，然后依次迭代計(jì)算擴(kuò)展至所有孩子。 ???將整個(gè)評分序列想象成為一個(gè)函數(shù)，接下來要做的是找到其中的極小值點(diǎn)，給它們分配糖果，再對其余的評分序列繼續(xù)找當(dāng)前的極小值點(diǎn)，分配糖果。直至分配結(jié)束。 ???想象一下快速排序的特點(diǎn)，每一次循環(huán)會(huì)確定一個(gè)最終排序結(jié)束時(shí)元素的位置。而目前的這個(gè)思路和它類似：每一次會(huì)確定若干個(gè)極小值點(diǎn)的糖果數(shù)。

??????所以具體的算法思路如下：
??????如果一個(gè)孩子的左右兩側(cè)評分都大于等于它，那么它就是一個(gè)極小值。
??????(1) 找到所有極小值點(diǎn)，將它們對應(yīng)的糖果數(shù)量置為1
??????(2) 排除上述已經(jīng)分配了糖果的孩子，在其余孩子中再次找極小值點(diǎn)，將它們對應(yīng)的糖果數(shù)量置為2.（每一輪的極小值點(diǎn)分配的糖果數(shù)要比之前的多1個(gè)）
??????(3) 不斷重復(fù)步驟2. 直至給所有的孩子都分配了糖果。

??????對上面的示例進(jìn)行分析：給定孩子的評分?jǐn)?shù)組為 { 1,0,2,3,4,3,2,2 }
??????第一輪之后糖果數(shù)組為：_ 1 _ _ _ _ 1 1 ，其中第二個(gè)數(shù) 0 ，倒數(shù)第二個(gè)數(shù) 2 和最后一個(gè)數(shù) 2 為極小值。

??????第二輪在第一輪的基礎(chǔ)之上，得到兩個(gè)孩子的評分區(qū)間分別為：{ 1 } 和 { 2,3,4,3} 。對這兩個(gè)數(shù)組找它們的極小值，給這些極小值點(diǎn)的糖果數(shù)為2，得到第二輪之后糖果數(shù)組為：2 1 2 _ _ 2 1 1 ，其中區(qū)間 1 中唯一的一個(gè)數(shù) 1 是極小值，區(qū)間 2 中的第一個(gè)數(shù) 2 和最后一個(gè)數(shù) 3 為極小值。

??????第三輪在第二輪的基礎(chǔ)之上，得到一個(gè)孩子的評分區(qū)間分別為：{ 3,4} 。對這個(gè)數(shù)組找極小值，給這些極小值點(diǎn)的糖果數(shù)為3，得到第三輪之后糖果數(shù)組為：2 1 2 3 _ 2 1 1 ，其中第一個(gè)數(shù) 3 為最小值。

??????第四輪在第三輪的基礎(chǔ)之上，得到一個(gè)孩子的評分區(qū)間分別為：{ 4} 。對這個(gè)數(shù)組找極小值，給這些極小值點(diǎn)的糖果數(shù)為4，得到第四輪之后糖果數(shù)組為：2 1 2 3 4 2 1 1 ，這個(gè)唯一的數(shù)為極小值。

??????糖果數(shù)：{ 2,1,2,3,4,2,1,1 }即為最終結(jié)果。

三、搞點(diǎn)實(shí)際點(diǎn)兒的（C++實(shí)現(xiàn)）

1.略顯粗糙的代碼實(shí)現(xiàn)

??????說明：下面的代碼有助于對整體思路的把控，并且我在代碼中已經(jīng)給出了詳細(xì)的注釋。缺點(diǎn)是太繁瑣，提交的時(shí)候會(huì)報(bào)超時(shí)，我稍后會(huì)在此之上做一些優(yōu)化。
??????代碼如下：

class Solution { private:int count; //用來計(jì)數(shù)int start; //每一輪循環(huán)的起始下標(biāo)int end;//每一輪循環(huán)的結(jié)束下標(biāo)int assignCandy;//每一輪應(yīng)該給當(dāng)前極小值點(diǎn)的糖果數(shù)int sum; //求和，用來返回最終結(jié)果 public:int candy(vector<int>& ratings) {int N = ratings.size();//為幾個(gè)參數(shù)設(shè)置初始值count = 0;sum = 0;assignCandy = 1;start = 0;end = N - 1;int* flag = new int[N];//用來判斷哪些孩子已經(jīng)被分配了糖果，若分配了就置為1int* candys = new int[N];//保存給每一個(gè)孩子分配的糖果數(shù)目memset(flag, 0, sizeof(int)*N);//將flag數(shù)組初始時(shí)全置為0setCandy(ratings, flag, candys);//第一輪分配，找到本輪的極小值點(diǎn)，并進(jìn)行糖果分配//在第一輪分配之后，這里采用循環(huán)結(jié)構(gòu)來進(jìn)行每一輪的糖果分配，count表示當(dāng)前已經(jīng)分配了糖果的孩子數(shù)目，//所以退出條件這里寫作為 count<N while (count < N){assignCandy++;//每一輪待分配的糖果數(shù)量要比上一輪多1個(gè)for (int i = 0; i < N; i++)//遍歷一遍數(shù)組，以上一輪找到的極小值點(diǎn)為基礎(chǔ)，得到本輪應(yīng)該分配糖果的孩子區(qū)間。{if (flag[i] == 0){start = i;while (i < N && flag[i] == 0)++i;end = i - 1;//每一次調(diào)用setCandy時(shí)，要先確定當(dāng)前區(qū)間的start和end。setCandy(ratings, flag, candys); }}}for (int i = 0; i < N; i++)sum += candys[i]; //最后得到所有的糖果數(shù)目return sum;}void setCandy(vector<int>& temp, int flag[], int candys[]){if (start == end) //如果區(qū)間里只有一個(gè)數(shù)的情況，那它就是本輪的極小值，直接分配糖果并返回{candys[start] = assignCandy;flag[start] = 1;count++;return;}int i, prev, after;//判斷區(qū)間的第一個(gè)數(shù)是否為極小值，只需要和第二個(gè)數(shù)相比較即可。 按照之前分析的，注意這里需要取等號。if (temp[start + 1] >= temp[start]){candys[start] = assignCandy;flag[start] = 1;count++;}//判斷區(qū)間的最后一個(gè)數(shù)是否為極小值，只需要和倒數(shù)第二個(gè)數(shù)相比較即可。 按照之前分析的，注意這里需要取等號。if (temp[end] <= temp[end - 1]){candys[end] = assignCandy;flag[end] = 1;count++;}for (prev = start, i = start + 1, after = start + 2; i <= end - 1; ++i, ++after, ++prev){//對區(qū)間中間的所有數(shù)依次遍歷，判斷是否為極小值，按照之前分析的，注意這里需要取等號。if (temp[i] <= temp[prev] && temp[i] <= temp[after]){candys[i] = assignCandy;flag[i] = 1;count++;}}}};

??????需要指出一點(diǎn)，也是之前困擾了我比較久的一個(gè)問題。上面這個(gè)代碼，在while(count<N)循環(huán)中，有一行代碼我之前是寫成這樣的：

...while (flag[i] == 0 && i < N)++i;...

??????然后呢，它在VS2017中是可以編譯并運(yùn)行的，但是在LeetCode中會(huì)報(bào)錯(cuò)：“AddressSanitizer: heap-buffer-overflow on address…” ，個(gè)人猜測，在VS中對 && 應(yīng)該是有做過優(yōu)化的，而在LeetCode中是嚴(yán)格按照從左到右來判斷的，所以會(huì)出現(xiàn)數(shù)組訪問越界的現(xiàn)象。 解決方法：把 && 的左右互換一下就行。先判斷 i<N 就好了。

---

2.稍顯精致的代碼實(shí)現(xiàn)

??????上面這個(gè)代碼因?yàn)樵谔峤粫r(shí)會(huì)報(bào)超時(shí)，所以需要進(jìn)行邏輯上的刪減，去掉多余的部分。這次的代碼采用遞歸來實(shí)現(xiàn)，我依然會(huì)給出詳細(xì)的注釋。
代碼如下：

class Solution { private:int sum;//用來保存最終的糖果數(shù)，進(jìn)行返回 public:int candy(vector<int>& ratings) {int N = ratings.size();sum = 0;int assignCandy = 1;//初始對每個(gè)極小值點(diǎn)分發(fā)的糖果數(shù)為1int start = 0; //第一輪循環(huán)的起始下標(biāo)int end = N - 1; //第一輪循環(huán)的結(jié)束下標(biāo)//這里就不需要 candys 和 flag 數(shù)組了哦setCandy(ratings, start, end, assignCandy); //遞歸方法調(diào)用return sum;}void setCandy(vector<int>& temp,int start,int end, int assignCandy){//注意：sum在 一旦找到當(dāng)前輪次的極小值時(shí)，就會(huì)和當(dāng)前的assignCandy相加，從而構(gòu)成總的糖果數(shù)量。//如果區(qū)間長度為1的話，則它是一個(gè)極小值點(diǎn)，分配給它糖果，并將這個(gè)糖果數(shù)算在總數(shù)sum中。if (start == end){sum += assignCandy;return;}else if (start > end)//如果在兩個(gè)極小值接連出現(xiàn)時(shí)，會(huì)出現(xiàn)這種情況， 直接返回即可，因?yàn)閮蓚€(gè)極小值之間沒有元素了return;int i, prev, after;int startT = start, endT; //設(shè)置新的區(qū)間開始節(jié)點(diǎn)startT//處理第一個(gè)數(shù)，如果它是極小值的話if (temp[start + 1] >= temp[start]){sum += assignCandy;startT = start + 1;}for (prev = start, i = start + 1, after = start + 2; i <= end-1 ; ++i, ++after, ++prev){if (temp[i] <= temp[prev] && temp[i] <= temp[after]){sum += assignCandy;//一旦碰到一個(gè)極小值點(diǎn)，首先需要更新一下區(qū)間結(jié)束節(jié)點(diǎn)endTendT = i - 1;//對一個(gè)區(qū)間進(jìn)行遞歸方法調(diào)用，注意待分配的糖果數(shù)要加1setCandy(temp, startT, endT, assignCandy + 1);//注意：這里可能會(huì)發(fā)生startT大于endT的現(xiàn)象//還需要設(shè)置下一個(gè)區(qū)間的開始節(jié)點(diǎn)startTstartT = i + 1;}}//處理最后一個(gè)數(shù)，如果它是極小值的話if (temp[end] <= temp[end - 1]){sum += assignCandy;endT = end - 1;}elseendT = end;//對一次循環(huán)中的最后一個(gè)區(qū)間進(jìn)行分析setCandy(temp, startT, endT, assignCandy + 1);} };

---

3.最終的代碼實(shí)現(xiàn)

??????2 中的代碼解決了 1 中存在的問題，但是它有一個(gè)缺點(diǎn)。
??????當(dāng)測試用例為{20000,19999,19998,19997，…，4，3，2，1}時(shí)，這樣的逆序數(shù)組時(shí)，它的時(shí)間復(fù)雜度會(huì)急劇增大，是 2 中時(shí)間復(fù)雜度的 N 倍。所以，只好在 2 的基礎(chǔ)上加上了關(guān)于逆序的判斷；并且考慮到算法在完全升序排列的樣本上時(shí)間復(fù)雜度會(huì)增大，趨于O(N2)，所以在加上關(guān)于升序的判斷，這點(diǎn)可以參考快速排序的缺點(diǎn)。
??????整體上代碼的時(shí)間復(fù)雜度為O（lnN）,空間復(fù)雜度為O(lnN)，性能都還可以。得到最終的代碼如下：

class Solution { private:int sum; public:int candy(vector<int>& ratings) {int N = ratings.size();sum = 0;int assignCandy = 1;int start = 0;int end = N - 1;setCandy(ratings, start, end, assignCandy);return sum;}void setCandy(vector<int>& temp,int start,int end, int assignCandy){if (start == end){sum += assignCandy;return;}else if (start > end)return;//如果區(qū)間中的元素是降序排列的，那么直接計(jì)算sum的值即可。 采用等差數(shù)列求和公式來計(jì)算。if (isSorted_descend(temp, start, end)) {int j = end - start; //j+1個(gè)數(shù)。int temp = (j + 1)*assignCandy + ((end-start)*(j + 1)) / 2;sum += temp;return;}else if (isSorted_ascend(temp, start, end)) //判斷是否為升序{int j = end - start; //j+1個(gè)數(shù)。int temp = (j + 1)*assignCandy + ((end-start)*(j + 1)) / 2;sum += temp;return;}int i, prev, after;int startT = start, endT;if (temp[start + 1] >= temp[start]){sum += assignCandy;startT = start + 1;}for (prev = start, i = start + 1, after = start + 2; i <= end-1 ; ++i, ++after, ++prev){if (temp[i] <= temp[prev] && temp[i] <= temp[after]){sum += assignCandy;endT = i - 1;setCandy(temp, startT, endT, assignCandy + 1);startT = i + 1;}}if (temp[end] <= temp[end - 1]){sum += assignCandy;endT = end - 1;}elseendT = end;setCandy(temp, startT, endT, assignCandy + 1);}//判斷當(dāng)前區(qū)間的元素是否為降序排列。如果是，返回 1 如果兩個(gè)元素相同，則認(rèn)為非降序//結(jié)果為真表示是一個(gè)嚴(yán)格的降序序列int isSorted_descend(vector<int>& temp, int start, int end){while (start < end){if (temp[start] <= temp[start + 1])return 0;start++;}return 1;}//對是否是一個(gè)嚴(yán)格的升序序列的判定int isSorted_ascend(vector<int>& temp, int start, int end){while (start < end){if (temp[start] >= temp[start + 1])return 0;start++;}return 1;}};

4.提交結(jié)果

??????以 3 中的代碼進(jìn)行提交，結(jié)果如圖：

總結(jié)

??????最終的代碼實(shí)現(xiàn)整體上采用了遞歸的方法，也包含到了貪心和分治的思想。總算是按照自己的思路寫完了，挺費(fèi)勁的，道路是曲折的，但是結(jié)局是美好的~

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的LeetCode算法题0:分发糖果【贪心算法】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。