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.
不知道如何分析这个题，很自然的思路就是先假设一个结果数组存着每个孩子要拿的糖数，初始都为1。那么先从前往后遍历ratings数组，逐个比较每一项和其前面的“邻居”。如果遍历到的孩子评分比前面高，那么他的糖数就设置为前邻居糖数+1。遍历完之后还要反着再看一遍后邻居，如果比后邻居评分高，且糖数还不如后邻居多，那么就要设置成后邻居糖数+1。本质上就是先遍历一次，分别保证评分满足和左边的邻居比，之后再遍历一次，保证评分满足和右边的邻居比。最后把每个人手里糖数加起来就是结果。
Java
class Solution { public int candy(int[] ratings) { int len = ratings.length; int[] res = new int[len]; for (int i = 0; i < len; i++) res[i] = 1; for (int i = 1; i < len; i++) if (ratings[i-1] < ratings[i] ) res[i] = res[i-1] + 1; for (int i = len - 2; i >= 0; i--) if (ratings[i] > ratings[i+1] && res[i] <= res[i+1]) res[i] = res[i+1] + 1; int sum = 0; for (int num : res) sum += num; return sum; } }