題目描述（困難難度）
給 N 個(gè)小朋友分糖，每個(gè)人至少有一顆糖。并且有一個(gè) rating 數(shù)組，如果小朋友的 rating比它旁邊小朋友的 rating 大（不包括等于），那么他必須要比對(duì)應(yīng)小朋友的糖多。問(wèn)至少需要分配多少顆糖。
用 - 表示糖，舉幾個(gè)例子。
1 0 2
- - -
- -
總共就需要 5 顆糖。
1 2 2
- - -
-
總共就需要 4 顆糖。
解法一
根據(jù)題目，首先每個(gè)小朋友會(huì)至少有一個(gè)糖。
如果當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小，那么后一個(gè)小朋友的糖肯定是當(dāng)前小朋友的糖加 1。
比如 ration = [ 5, 6, 7] ，那么三個(gè)小朋友的糖就依次是 1 2 3。
如果當(dāng)前小朋友的 rating 比后一個(gè)小朋友的大，那么理論上當(dāng)前小朋友的糖要比后一個(gè)的小朋友的糖多，但此時(shí)后一個(gè)小朋友的糖還沒(méi)有確定，怎么辦呢？
參考 32題 的解法五，利用正著遍歷，再倒著遍歷的思想。
首先我們正著遍歷一次，只考慮當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小的情況。
接著再倒著遍歷依次，繼續(xù)考慮當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小的情況。因?yàn)橹耙呀?jīng)更新過(guò)一次糖果了，此時(shí)后一個(gè)小朋友的糖如果已經(jīng)比當(dāng)前小朋友的糖多了，就不需要進(jìn)行更新了。
舉個(gè)例子
初始化每人一個(gè)糖
1 2 3 2 1 4
- - - - - -.
只考慮當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小的情況,后一個(gè)小朋友的糖是當(dāng)前小朋友的糖加 1。
1 < 2
1 2 3 2 1 4
- - - - - -
-
2 < 3
1 2 3 2 1 4
- - - - - -
- -
-
3 > 2 不考慮
2 > 1 不考慮
1 < 4
1 2 3 2 1 4
- - - - - -
- - -
-
倒過(guò)來(lái)重新進(jìn)行
繼續(xù)考慮當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小的情況。此時(shí)后一個(gè)小朋友的糖如果已經(jīng)比當(dāng)前小朋友的糖多了，就不需要進(jìn)行更新。
4 1 2 3 2 1
- - - - - -
- - -
-
4 > 1 不考慮
1 < 2
4 1 2 3 2 1
- - - - - -
- - - -
-
2 < 3，3 的糖果已經(jīng)比 2 的多了，不需要考慮
3 > 2，不考慮
2 > 1，不考慮
所以最終的糖的數(shù)量就是上邊的 - 的和。
代碼的話，我們用一個(gè) candies 數(shù)組保存當(dāng)前的分配情況。
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
//每人發(fā)一個(gè)糖
for (int i = 0; i < n; i++) {
candies[i] = 1;
}
//正著進(jìn)行
for (int i = 0; i < n - 1; i++) {
//當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小,后一個(gè)小朋友的糖是當(dāng)前小朋友的糖加 1。
if (ratings[i] < ratings[i + 1]) {
candies[i + 1] = candies[i] + 1;
}
}
//倒著進(jìn)行
//下標(biāo)順序就變成了 i i-1 i-2 i-3 ... 0
//當(dāng)前就是第 i 個(gè)，后一個(gè)就是第 i - 1 個(gè)
for (int i = n - 1; i > 0; i--) {
//當(dāng)前小朋友的 rating 比后一個(gè)小朋友的小
if (ratings[i] < ratings[i - 1]) {
//后一個(gè)小朋友的糖果樹沒(méi)有前一個(gè)的多，就更新后一個(gè)等于前一個(gè)加 1
if (candies[i - 1] <= candies[i]) {
candies[i - 1] = candies[i] + 1;
}
}
}
//計(jì)算糖果總和
int sum = 0;
for (int i = 0; i < n; i++) {
sum += candies[i];
}
return sum;
}
時(shí)間復(fù)雜度：O（n）。
空間復(fù)雜度：O（n）。
解法二
參考 這里。
解法一中，考慮到
如果當(dāng)前小朋友的
rating比后一個(gè)小朋友的大，那么理論上當(dāng)前小朋友的糖要比后一個(gè)的小朋友的糖多，但此時(shí)后一個(gè)小朋友的糖還沒(méi)有確定，怎么辦呢？
之前采用了倒著遍歷一次的方式進(jìn)行了解決，這里再考慮另外一種解法。
考慮下邊的情況。
對(duì)于第 2 個(gè) rating 4，它比后一個(gè) rating 要大，所以要取決于再后邊的 rating，一直走到 2，也就是山底，此時(shí)對(duì)應(yīng)的糖果數(shù)是 1，然后往后走，走回山頂，糖果數(shù)一次加 1，也就是到 rating 4 時(shí)，糖果數(shù)就是 3 了。
再一般化，山頂?shù)奶枪麛?shù)就等于從左邊的山底或右邊的山底依次加 1 。
所以我們的算法只需要記錄山頂，然后再記錄下坡的高度，下坡的高度剛好是一個(gè)等差序列可以直接用公式求和。而山頂?shù)奶枪麛?shù)，取決于左邊山底到山頂和右邊山底到山頂?shù)哪膫€(gè)高度大。
而產(chǎn)生山底可以有兩種情況，一種是 rating 產(chǎn)生了增加，如上圖。還有一種就是 rating 不再降低，而是持平。
知道了上邊的想法，基本上就可以寫代碼了，每個(gè)人寫出來(lái)的應(yīng)該都不一樣，在 discuss 區(qū)也看到了很多不同的寫法，下邊說(shuō)一下我的思路。
抽象出四種情況，這里的高度不是 rating 進(jìn)行相減，而是從山底的 rating 到山頂?shù)?rating 經(jīng)過(guò)的次數(shù)。
-
左邊山底到山頂?shù)母叨却?，并且右邊山底后繼續(xù)增加。
-
左邊山底到山頂?shù)母叨却?，并且右邊山底是平坡?/p>
-
右邊山底到山頂?shù)母叨却螅⑶矣疫吷降缀罄^續(xù)增加。
-
右邊山底到山頂?shù)母叨却螅⑶矣疫吷降资瞧狡隆?/p>
有了這四種情況就可以寫代碼了。
我們用 total 變量記錄糖果總和， pre 變量記錄前一個(gè)小朋友的糖果數(shù)。如果當(dāng)前的 rating 比前一個(gè)的 rating 大，那么說(shuō)明在走上坡，可以把前一個(gè)小朋友的糖果數(shù)加到 total 中，并且更新 pre 為當(dāng)前小朋友的糖果數(shù)。
如果當(dāng)前的 rating 比前一個(gè)的 rating 小，說(shuō)明開始走下坡，用 down 變量記錄連續(xù)多少次下降，此時(shí)的 pre 記錄的就是從左邊山底到山底的高度。當(dāng)出現(xiàn)平坡或上坡的時(shí)候，將所有的下坡的糖果數(shù)利用等差公式計(jì)算。此外根據(jù) pre 和 down 決定山頂?shù)奶枪麛?shù)。
根據(jù)當(dāng)前是上坡還是平坡，來(lái)更新 pre。
大框架就是上邊的想法了，還有一些邊界需要考慮一下，看一下代碼。
public int candy(int[] ratings) {
int n = ratings.length;
int total = 0;
int down = 0;
int pre = 1;
for (int i = 1; i < n; i++) {
//當(dāng)前是在上坡或者平坡
if (ratings[i] >= ratings[i - 1]) {
//之前出現(xiàn)過(guò)了下坡
if (down > 0) {
//山頂?shù)奶枪麛?shù)大于下降的高度，對(duì)應(yīng)情況 1
//將下降的糖果數(shù)利用等差公式計(jì)算，單獨(dú)加上山頂
if (pre > down) {
total += count(down);
total += pre;
//山頂?shù)奶枪麛?shù)小于下降的高度，對(duì)應(yīng)情況 3，
//將山頂也按照等差公式直接計(jì)算進(jìn)去累加
} else {
total += count(down + 1);
}
//當(dāng)前是上坡，對(duì)應(yīng)情況 1 或者 3
//更新 pre 等于 2
if (ratings[i] > ratings[i - 1]) {
pre = 2;
//當(dāng)前是平坡，對(duì)應(yīng)情況 2 或者 4
//更新 pre 等于 1
} else {
pre = 1;
}
down = 0;
//之前沒(méi)有出現(xiàn)過(guò)下坡
} else {
//將前一個(gè)小朋友的糖果數(shù)相加
total += pre;
//如果是上坡更新當(dāng)前糖果數(shù)是上一個(gè)的加 1
if (ratings[i] > ratings[i - 1]) {
pre = pre + 1;
//如果是平坡，更新當(dāng)前糖果數(shù)為 1
} else {
pre = 1;
}
}
} else {
down++;
}
}
//判斷是否有下坡
if (down > 0) {
//和之前的邏輯一樣進(jìn)行相加
if (pre > down) {
total += count(down);
total += pre;
} else {
total += count(down + 1);
}
//將最后一個(gè)小朋友的糖果計(jì)算
} else {
total += pre;
}
return total;
}
//等差數(shù)列求和
private int count(int n) {
return (1 + n) * n / 2;
}
這個(gè)算法相對(duì)于解法一的好處就是將空間復(fù)雜度從 O(n) 優(yōu)化到了 O(1)。
總
解法一雖然空間復(fù)雜度大一些，但是很好理解，正著遍歷，倒著遍歷的思想，每次遇到都印象深刻。解法二主要是對(duì)問(wèn)題進(jìn)行深入考慮，雖然麻煩些，但空間復(fù)雜度確實(shí)優(yōu)化了。
更多詳細(xì)通俗題解詳見(jiàn) leetcode.wang 。
