LeetCode 135 分發糖果（Candy）
135. 分發糖果
題目的👍：1149
題目的👎：173
1、題目描述
老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分，
你需要按照以下要求，幫助老師給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果，
相鄰的孩子中，評分高的孩子必須獲得更多的糖果，
那么這樣下來，老師至少需要準備多少顆糖果呢？
示例 1:
輸入: [1,0,2]
輸出: 5
解釋: 你可以分別給這三個孩子分發 2、1、2 顆糖果，
示例 2:
輸入: [1,2,2]
輸出: 4
解釋: 你可以分別給這三個孩子分發 1、2、1 顆糖果，
第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件，
2、方法和思路
這個問題在我看來仍然是一個山脈陣列的問題（山脈例如：1，2，3，4，2，2，1），在本題中幾乎仍然符合這個規律,不過山頂和山底的定義需要改變，例如這樣的幾個分數 :
| 1 | 2 | 3 | 2 | 2 | 2 | 1 |
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
按照普通的山脈來說，山頂是A[3]，左山底位A[0],右山底為A[6]，并不需要嚴格遞減，然而在本題中的描述，山脈陣列必須是嚴格遞減的，例如[2,3,3]的分數我們分配的糖果為[1,2,1]，即右邊的3也是山底，回到上面的例子，我們就把陣列分為兩個“山脈”，[1,2,3,2,2], [2,2,1] (重疊的一部分需要剪掉)，分配的糖果即為[1,2,3,1,1],[1,2,1]，因此，我們便需要用雙指標的方法來找到每個山脈，然后再計算每個山脈應該分配的糖果數即可，這種方法也不需要使用額外陣列（其實也沒想到用額外陣列怎么做）
3、代碼
class Solution {
class Solution {
public int candy(int[] ratings) {
int start = 0;
int res = 0;
int length = ratings.length;
while(true) {
while(start+1 < length && ratings[start+1] == ratings[start]) {
//重復的山底置為1，因為計算右邊山底的時候是不計算等于的情況的，需要這樣去掉
++start;
++res;
}
int left = start;//左山底
while(start+1 < length && ratings[start+1] > ratings[start]) {
++start;
}
int top = start;//山頂
while(start+1 < length && ratings[start+1] < ratings[start]) {
++start;
}
int right = start;//右山底
int num1 = 1;
int num2 = 1;
while(ratings[left] != ratings[top]) {
res+=num1;
if(ratings[left] != ratings[left+1]) ++num1;
++left;
}
while(ratings[right] != ratings[top]) {
res+=num2;
if(ratings[right-1] != ratings[right]) ++num2;
--right;
}
res-=1;//這邊希望計算右邊時不計算右山底，下輪迭代時再計算，避免重復
if(left == right) res+=Math.max(num1,num2);
else { //多個山頂的情況
res+=Math.max(num1,num2);
res+=Math.min(num1,num2)*(right-left);
}
if(start+1 == length) return res+1;
}
}
}
4、復雜度
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/197108.html
標籤：其他