一、題目

有N個(gè)孩子站成一排，每個(gè)孩子有一個(gè)分值?，F(xiàn)在你需要為這些孩子分配糖果，但需要滿足下面的需求：

• 每個(gè)孩子至少分一個(gè)。
• 擁有較高分值的孩子得到的糖果要比與他相鄰的孩子得到的數(shù)量多

那么最少需要給這些孩子分配多少糖果？

二、分析

1、如果孩子當(dāng)前的分值大于前一個(gè)孩子，當(dāng)前孩子分得糖果數(shù)量應(yīng)該是 前一個(gè)孩子分得糖果數(shù)加1。
下圖中curr代表當(dāng)前孩子，圖中上半部分對(duì)應(yīng)每個(gè)孩子的分值，下半部分對(duì)應(yīng)每個(gè)孩子分配的糖果數(shù).
后文中此類圖形同理。

2、如果當(dāng)前孩子的分值等于前一個(gè)孩子的分值，則當(dāng)前孩子所分得糖果數(shù)量應(yīng)該是1。（注意題干是：分配最少糖果）

3、如果連續(xù)下降的，如果當(dāng)前孩子的分值小于前一個(gè)孩子的分值，我們還不能得出當(dāng)前位置的糖果數(shù)是多少（不知道有多少連續(xù)下降數(shù)），繼續(xù)看下面

孩子所具有的分值連續(xù)下降時(shí)，那么我們使用countDown來(lái)存放連續(xù)下降數(shù)。下圖中，在curr位置處countDown = 2。(3-2，2-1)

如果在下降序列中，當(dāng)前值等于前一個(gè)人的值或大于前一個(gè)人的值，那么不在構(gòu)成下降序列，那么我們將通過(guò)數(shù)列求和公式來(lái)計(jì)算這段連續(xù)下降序列的長(zhǎng)度。下圖為等差數(shù)列求和公式。

當(dāng)計(jì)算下降區(qū)間長(zhǎng)度時(shí)，需要考慮pre變量。下圖中pre為2，因此接下來(lái)的兩次糖果分配數(shù)量，無(wú)法按依次遞減的方式分配，因?yàn)檫@樣，因此第2次分配的數(shù)量將會(huì)是0，而每個(gè)孩子最少要分配一個(gè)。

在這種情況下，countDown >= prew，這樣我們需要修改pre位置處為孩子分配的糖果數(shù)，pre = countdown – pre + 1。修正后可以保證每個(gè)孩子至少分配一個(gè)。

三、代碼實(shí)現(xiàn)

public static int candy(int[] ratings) {/*** pre:前面元素能夠得到的糖數(shù)* countDown:連續(xù)下降數(shù)* total:最少分配的糖果數(shù)*/int pre = 1, countDown = 0, total = 1;for (int i = 1; i < ratings.length; i++) {if (ratings[i] >= ratings[i - 1]) { //當(dāng)前元素大于等于前一元素if (countDown > 0) {total += countDown * (countDown + 1) / 2;if (countDown >= pre) {total += countDown - pre + 1;}pre = 1;countDown = 0;}//如果當(dāng)前元素等于前一元素，則當(dāng)前元素為1，否則，當(dāng)前元素+1pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;total += pre;} else { //當(dāng)前元素小于前一元素countDown++;}}if (countDown > 0) {total += countDown * (countDown + 1) / 2;if (countDown >= pre) {total += countDown - pre + 1;}}return total;}

四、鳴謝

文章1：http://www.allenlipeng47.com/blog/index.php/2016/07/21/candy/
文章2：https://blog.csdn.net/revivedsun/article/details/52897147

總結(jié)

以上是生活随笔為你收集整理的算法—分配糖果的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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