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.
分发糖果。
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路是贪心。根据题意，我们需要对input数组扫描两遍，因为对于每个孩子来说，他拥有的糖果数需要同时和他的左右邻居比较以确保满足题意。所以我们创建两个和input数组等长的数组，left数组从左往右扫描，right数组从右往左扫描。
更新left数组的方式是，对于每个孩子，需要看他的评分是否大于他左边的孩子的评分，如果大于，当前这个孩子的糖果数起码是他左边孩子的糖果数 + 1。我们以这种方式从左往右更新left数组。
更新right数组的方式是，对于每个孩子，需要看他的评分是否大于他右边的孩子的评分，如果大于，当前这个孩子的糖果数起码是他右边孩子的糖果数 + 1。我们以这种方式从右往左更新right数组。在更新right数组的同时，我们可以得到相同位置上left数组和right数组之间的较大值，这个较大值即是当前位置上的孩子需要拥有的糖果数。
最后附上一个动图帮助理解。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public int candy(int[] ratings) {
3 int[] left = new int[ratings.length];
4 int[] right = new int[ratings.length];
5 Arrays.fill(left, 1);
6 Arrays.fill(right, 1);
7 for (int i = 1; i < ratings.length; i++) {
8 if (ratings[i] > ratings[i - 1]) {
9 left[i] = left[i - 1] + 1;
10 }
11 }
12 int count = left[ratings.length - 1];
13 for (int i = ratings.length - 2; i >= 0; i--) {
14 if (ratings[i] > ratings[i + 1]) {
15 right[i] = right[i + 1] + 1;
16 }
17 count += Math.max(left[i], right[i]);
18 }
19 return count;
20 }
21 }