1619. Candy II

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.
• Children with the same rating and are located next to each other get the same candies.

What is the minimum candies you must give?

Have you met this question in a real interview?  

Example

Example 1:

Input: 4 7 8 1 6 6 2
Output: 12

Explanation: 1 + 2 + 3 + 1 + 2 + 2 + 1 = 12

Example 2:

Input: 10 2 3 3 7 10
Output: 14

Explanation: 2 + 1 + 2 + 2 + 3 + 4 = 14

class Solution { public: /** * @param ratings: rating value of each child * @return: Return the minimum candies you must give. */ int candyII(vector<int> &ratings) { // write your code here const int size = ratings.size(); if(size == 0){ return 0; } vector<int> candy(size, 1); for(int i = 1; i < size; i++){ if(ratings[i] > ratings[i - 1]){ candy[i] = candy[i - 1] + 1; } if(ratings[i] == ratings[i - 1]){ candy[i] = candy[i - 1]; } } int res = 0; for(int i = size - 1; i > 0; i--){ if(ratings[i - 1] > ratings[i] && candy[i - 1] <= candy[i]){ candy[i - 1] = candy[i] + 1; } else if(ratings[i - 1] == ratings[i]){ candy[i] = candy[i - 1] = max(candy[i], candy[i - 1]); } res += candy[i]; } res += candy[0]; return res; } };