題目
有 n 個孩子排成一排，陣列 ratings 中代表每個孩子的分數，你可以送這些小朋友糖果，但需符合以下要求：
- 每個孩子必須至少擁有一顆糖果。
- 得分較高的孩子比旁邊的孩子要獲得更多醣果。
返回分給孩子們所需的最少糖果數量。
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Constraints:
n == ratings.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104
解題思路
每個孩子需要和左右兩邊的小孩比較，如果同時和左右邊比較很容易出錯，所以可以分開比較。
分別確認：
- 右邊的小孩比左邊的小孩得分高
- 左邊的小孩比右邊的小孩得分高
- 取最大值即為每個孩子被分發的最少糖果數
ratings: [1,2,2,5,4,3,2]
=>candy_left: [1,2,1,2,1,1,1] // 1.右邊的小孩比左邊的小孩得分高
=>candy_right: [1,1,1,4,3,2,1] // 2.左邊的小孩比右邊的小孩得分高
=>candy: [1,2,1,4,3,2,1] // 3.取最大值程式碼
/**
* @param {number[]} ratings
* @return {number}
*/
var candy = function(ratings) {
let candy = new Array(ratings.length).fill(1)
// 1. 只看右比左大的情況，前至後遍歷
for (let i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candy[i] = candy[i - 1] + 1
}
}
// 2. 只看左比右大的情況，後至前遍歷
for (let i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candy[i] = Math.max(candy[i + 1] + 1, candy[i])
}
}
return candy.reduce((acc, cur) => acc + cur, 0)
};
