LeetCode: 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.

解题思路

虽然题目标签写的是 Hard，但实际上这道题并不难。
只需要根据相对大小关系，以最小的份额分配 candy 即可。也就是说某孩子拿到的糖果是左边孩子 rating 升序到该孩子的序号，和该孩子 rating 降序到最右边的最大值。

例如：rating 的相对大小如初始状态的分配

• 初始状态

• 首先一人一份糖果在手， 保证最小份额
  
• 根据 rating 升序情况，给连续升序子序列的孩子分配最小份额，即升序的序号
  
• 根据 rating 降序情况，给连续降序子序列的孩子分配最小份额，即降序倒数序号
  
• 调整升序降序交界处的孩子糖果份额，取升/降序计算结果的较大值
  

AC 代码

class Solution 
{
public:
    int candy(vector<int>& ratings) 
    {
        vector<int> childrenCandy(ratings.size(), 1);

        // 升序
        for(size_t i = 1; i < ratings.size(); ++i)
        {
            if(ratings[i-1] < ratings[i])
            {
                childrenCandy[i] = childrenCandy[i-1]+1;
            }
        }

        // 降序
        for(size_t i = ratings.size()-1; i > 0; --i)
        {
            if(ratings[i-1] > ratings[i])
            {
                // 调整？
                childrenCandy[i-1] = max(childrenCandy[i-1], childrenCandy[i]+1);
            }
        }

        // 统计
        int count = 0;
        for(int candyNum : childrenCandy)
        {
            count += candyNum;
        }

        return count;
    }
};