Candy

Link

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

Deadline

Jul 10, 2022

Status

Archived

Type

greedy

Array

문제

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

풀이

은찬


var candy = function(ratings) {
    const { length } = ratings;
    const fromLeft = Array.from({length}, () => 1);
    const fromRight = Array.from({length}, () => 1);
    let answer = 0;
    
    for(let i = 1; i < length; i++){
        const current = ratings[i];
        const before = ratings[i - 1];
        
        if(current > before){
            fromLeft[i] = fromLeft[i - 1] + 1;
        }
    }
    
    for(let i = length - 2; i >= 0; i--){
        const current = ratings[i];
        const next = ratings[i + 1];
        
        if(current > next){
            fromRight[i] = fromRight[i + 1] + 1;
        }
    }
    
    for(let i = 0; i < length; i++){
        answer += Math.max(fromLeft[i], fromRight[i]);
    }
    
    return answer;
};

효성) 왕어렵군요! 은찬님 풀이 참고해서 제출할게요오