題目

https://leetcode.com/problems/candy/

題解

思路

首先，根據題意，這是一個分糖果問題。本題需要滿足兩個條件：

每個孩子至少有一個糖果

rating 值較大的孩子，得到的糖果也較多（rating 值相等時隨意）

通過分析可以發現，rating 值 本質上在確定 前后孩子 分到的糖果的 大小關系，也就是確定了前后之間的 單調性。而具體分到多少糖果與 rating 值無關，是由單調性決定的。

舉一個例子，假設我們有下面這個序列：

8 4 4 3 9 2 5 5 9 9 9 1 2 2

我們比較后一個數字與前一個數字的大小關系，記為 help[]。

• 若大于，則記為 ↑
• 若小于，則記為 ↓
• 若等于，則記為 ？

得到下面這個結果：

觀察上面這個結果，它表示了前后之間的單調關系，現在我們需要根據這個單調關系，給每一個位置分糖果。

一個簡單的思路是貪心法。我們希望所有糖果的總數最小，就要從左向右開始，讓每個位置上的糖果數量都最小。而由于需要保證每個孩子至少有一個糖果，所以我們 無法直接確定第一個孩子應該得到多少糖果，因為他會受到后面糖果數量的影響。

如果連第一個孩子的糖果數量都不能確定，那還怎么繼續啊？沒關系，對于每一個位置 n，我們 暫且分給他最少的糖果，讓他能暫時滿足當前的位置（n-1 和 n 的關系）就可以了。你可能要問了，后面的孩子怎么辦？后面再調整 就好了。

舉一個具體的例子，如下圖。

對于 第 0 個位置 來說，因為它是 ?，所以他無欲無求，不和前面的孩子攀比，容易滿足。目前只要給他 1 個糖果 就夠了。

對于 第 1 個位置 來說，因為它是 ↓，所以他要比前面的孩子糖果少。為了保證不浪費，我們對糖果的增減幅度都為1。所以，第 1 個位置的糖果數量要比第 0 個位置的糖果數量少 1 個，也就是給第 1 個位置的孩子 0 個糖果 。那么問題來了，說好每個孩子至少有 1 個糖果呢？這個問題先放著，待會兒再調整。

下面來到 第 2 個位置。因為它是 ?，又是一個無欲無求的容易滿足的孩子。這時候我們發現，對于無欲無求的孩子，不管前面的位置有多少糖果，我們 只要給他 1 個糖果就夠了。它不受前面的影響，相當于 新開一個序列。新序列的開始，意味著上一個序列的結束。所以，在開啟新序列之前，我們需要對上一個結束的序列進行 清算！
清算的時候，要保證上一個序列中每個孩子至少有 1 個糖果，所以要找到上一個序列中 糖果數量最少的孩子對應的糖果數量，這個值可能為負數。此時需要給每個孩子增加相同數量的糖果，直到這個糖果最少的孩子有 1 個糖果為止。其中，給上一序列中的每個孩子同時加相同數量的糖果，是為了滿足前后單調關系。

另外，還有一種情況可以 新開序列，就是當 help 數組出現 ↑↓ 這種組合的時候，這個 ↓ 暫時不受前面糖果數量的約束，只需要給 1 個糖果就夠了（引入了一個小坑，后面講）。

后面的位置以此類推，就省略了。得到的結果應該是這樣的：

清算的過程，需要照顧到前一個序列的末尾

上述清算的過程其實會引入一個小坑，只不過上面的數組比較特殊，沒有發現而已。我們看下面這個例子。

為了便于描述，我們藍框內的序列分別稱作 序列1，序列2，序列3。

前面的過程看起來很正常，直到 index=7 的時候，問題出現了。此時我們需要 清算序列3，為了滿足最少糖果數量要求，需將 1, 0 改為 2, 1。這時候序列 2 不開心了。在此之前，序列 2 末尾糖果數量是 2，index=4 位置的糖果是要比 index=5 位置的糖果多的。可現在 index=4,5 兩個位置的糖果數量相等了，index=4 的孩子當然不愿意。

怎么辦呢？給 index=4 的孩子補充糖果唄，直到他的糖果比 index=5 的糖果多為止。你可能會擔心，給 index=4 的孩子補充糖果的操作，是否會引起他的前一個的孩子的不滿？可以證明的是，不會存在這種情況。因為 根據序列的劃分，只有在 ↑↓ 或 ? 的是時候才會新開序列，而在這兩種情況中，只有在出現 ↑↓ 這種關系的時候，補充糖果操作才可能影響到前面的孩子，因為 ? 情況下的孩子是無欲無求的，他既可以比前面多，也可以比前面少。因此，增加判斷條件（對應代碼中的 line 20），使得需要補充糖果的孩子在 help 數組中肯定是個 ↑，說明他的糖果數本來就比前面的孩子多，所以無論增加多少，也不為過了。

上面這段話可能說的有點繞，總結起來就是：在 index=7 的時候清算 序列3，在清算的過程影響到了前一個序列的末尾，所以要給 序列2 的末尾補充糖果。

至此，整個清算過程就結束了。最后需要注意的是，到 for 循環結束時，是無法觸發最后一個序列的清算的，最后一個序列需要獨立清算。

代碼

class Solution {public int candy(int[] ratings) {int[] help = new int[ratings.length]; // 含義：1=↑ 2=↓ 3=?help[0] = 3;for (int i = 1; i < ratings.length; i++) {if (ratings[i] > ratings[i - 1]) help[i] = 1;else if (ratings[i] < ratings[i - 1]) help[i] = 2;else help[i] = 3;}int min = 1; // 當前序列最小糖果數量int sum = 1; // 全部糖果數量int cur = 1; // 當前位置需要糖果數量int count = 1; // 當前序列長度int curFirst = 1; // 當前序列起始位置糖果數量int preLast = Integer.MAX_VALUE; // 前一序列末尾位置糖果數量for (int i = 1; i < help.length; i++) {if (help[i] == 2 && help[i - 1] == 1 || help[i] == 3) { // ↑↓ 或 ?// 清算前一序列curFirst = curFirst + (1 - min);if (help[i - count] == 2) sum += Math.max(curFirst - preLast + 1, 0);preLast = cur + (1 - min); // ↑↓sum += (1 - min) * count;// 新開一個序列min = cur = curFirst = 1;count = 0;} else if (help[i] == 2) { // ↓cur -= 1;min = Math.min(min, cur);} else { // ↑cur += 1;min = Math.min(min, cur);}sum += cur;count++;}// 獨立清算最后一個序列min = Math.min(min, cur);curFirst = curFirst + (1 - min);if (help[help.length - count] == 2) sum += Math.max(curFirst - preLast + 1, 0);sum += (1 - min) * count;return sum;} }

補一張草稿：

第一次做 hard 題，寫了 2.5h。。時間主要花在調整細節、以及初始思路沒有照顧到的地方導致的 bug 上了。再接再厲吧~

總結

以上是生活随笔為你收集整理的leetcode 135. Candy | 135. 分发糖果（原创图文详解，Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

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