135. Candy

There are N children standing in a line. Each child is assigned a rating value.

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.

What is the minimum candies you must give?

Example 1:

Input: [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: [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.

Rust Solution

struct Solution;

impl Solution {
    fn candy(ratings: Vec<i32>) -> i32 {
        let n = ratings.len();
        let mut count: Vec<i32> = vec![1; n];
        for i in 1..n {
            if ratings[i] > ratings[i - 1] {
                count[i] = count[i].max(count[i - 1] + 1);
            }
        }
        for i in (0..n - 1).rev() {
            if ratings[i] > ratings[i + 1] {
                count[i] = count[i].max(count[i + 1] + 1);
            }
        }
        count.into_iter().sum()
    }
}

#[test]
fn test() {
    let ratings = vec![1, 0, 2];
    let res = 5;
    assert_eq!(Solution::candy(ratings), res);
    let ratings = vec![1, 2, 2];
    let res = 4;
    assert_eq!(Solution::candy(ratings), res);
    let ratings = vec![1, 3, 2, 2, 1];
    let res = 7;
    assert_eq!(Solution::candy(ratings), res);
}

Having problems with this solution? Click here to submit an issue on github.