分發(fā)糖果
n 個孩子站成一排吟逝。給你一個整數(shù)數(shù)組 ratings 表示每個孩子的評分俩由。
你需要按照以下要求，給這些孩子分發(fā)糖果：
- 每個孩子至少分配到
1個糖果。 - 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。
請你給每個孩子分發(fā)糖果，計算并返回需要準備的 最少糖果數(shù)目 止潘。
示例 1：
輸入：ratings = [1,0,2]
輸出：5
解釋：你可以分別給第一個、第二個辫诅、第三個孩子分發(fā) 2凭戴、1、2 顆糖果炕矮。
示例 2：
輸入：ratings = [1,2,2]
輸出：4
解釋：你可以分別給第一個么夫、第二個、第三個孩子分發(fā) 1吧享、2魏割、1 顆糖果。
第三個孩子只得到 1 顆糖果钢颂，這滿足題面中的兩個條件钞它。
方法一：兩次遍歷
我們可以將「相鄰的孩子中，評分高的孩子必須獲得更多的糖果」這句話拆分為兩個規(guī)則殊鞭，分別處理遭垛。
- 左規(guī)則：當 ratings[i?1]<ratings[i] 時，i 號學生的糖果數(shù)量將比 i - 1 號孩子的糖果數(shù)量多操灿。
- 右規(guī)則：當 ratings[i]>ratings[i+1] 時锯仪，i 號學生的糖果數(shù)量將比 i + 1 號孩子的糖果數(shù)量多。
我們遍歷該數(shù)組兩次趾盐，處理出每一個學生分別滿足左規(guī)則或右規(guī)則時庶喜，最少需要被分得的糖果數(shù)量。每個人最終分得的糖果數(shù)量即為這兩個數(shù)量的最大值救鲤。
public int candy(int[] ratings) {
int n = ratings.length;
int res = 0;
int[] left = new int[n];
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
int right = 0;
for (int j = n - 1; j >= 0; j--) {
if (j < n - 1 && ratings[j] > ratings[j + 1]) {
right = Math.max(right + 1, left[j]);
} else {
right = left[j];
}
res += right;
}
return res;
}
方法二：常數(shù)空間
從左到右枚舉每一個同學久窟，記前一個同學分得的糖果數(shù)量為 pre：
- 如果比上一個分數(shù)高，則當前分到pre+1
- 如果更低本缠，則給該同學分一個斥扛，并把該同學所在的遞減序列中所有的同學都再多分配一個糖果，以保證糖果數(shù)量還是滿足條件丹锹。
- 我們無需顯式地額外分配糖果稀颁，只需要記錄當前的遞減序列長度芬失，即可知道需要額外分配的糖果數(shù)量。
- 同時注意當當前的遞減序列長度和上一個遞增序列等長時匾灶，需要把最近的遞增序列的最后一個同學也并進遞減序列中棱烂。
ratings 3 6 8 5 4 2 1 0
1 2 3 1
1 2 3 1+1=2 1
1 2 3+1=4 2+1=3 1+1=2 1
1 2 4+1=5 3+1=4 2+1=3 1+1=2 1
1 2 5+1=6 4+1=5 3+1=2 2+1=1 1+1=2 1
public int candy(int[] ratings) {
int n = ratings.length;
int res = 1;
// 記錄遞增序列的長度，包括自身
int incrLen = 1;
// 記錄遞減序列的長度粘昨，如3 2 1 到最后是長度為2垢啼，因為默認將3算到了遞增序列
int decLen = 0;
// 前一個分到的糖果
int pre = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] >= ratings[i - 1]) {
decLen = 0;
if (ratings[i] == ratings[i - 1]) {
pre = 1;
} else {
pre++;
}
res += pre;
incrLen = pre;
} else {
decLen++;
// 當遞減序列和遞增序列長度相等時 3 6 [8] 4 2 1
// 相當于每一輪給考慮8時多分一個
if (decLen == incrLen) {
decLen++;
}
res += decLen;
pre = 1;
}
}
return res;
}
