135. Candy.js.md

135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

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.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

Solution 1: 贪心 (Greedy)

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
    const candies = new Array(ratings.length).fill(1);
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = Math.max(candies[i], candies[i - 1] + 1);
        }
    }
    for (let i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }
    return candies.reduce((sum, candy) => sum + candy);
};

Solution 2：动态规划 (Dynamic Programming)

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
    const indexes = ratings.map((rating, index) => index).sort((a, b) => ratings[a] - ratings[b]);
    const candies = new Array(ratings.length).fill(1);
    for (let i = 0; i < indexes.length; i++) {
        const index = indexes[i];
        if (index > 0 && ratings[index - 1] > ratings[index]) {
            candies[index - 1] = Math.max(candies[index - 1], candies[index] + 1);
        }
        if (index < ratings.length - 1 && ratings[index + 1] > ratings[index]) {
            candies[index + 1] = Math.max(candies[index + 1], candies[index] + 1);
        }
    }
    return candies.reduce((prev, current) => prev + current);
};