412. 分糖果
有
N
个小孩站成一列。每个小孩有一个评级。给定数组
ratings
代表这些小孩的评级。
现在你需要按照以下要求,给小孩们分糖果:
-
每个小孩至少得到一颗糖果。
-
评级越高的小孩可以比他相邻的两个小孩得到更多的糖果。
你最少要准备多少糖果?
样例
Example 1:
Input: [1, 2]
Output: 3
Explanation: Give the first child 1 candy and give the second child 2 candies.
Example 2:
Input: [1, 1, 1]
Output: 3
Explanation: Give every child 1 candy.
Example 3:
Input: [1, 2, 2]
Output: 4
Explanation:
Give the first child 1 candy.
Give the second child 2 candies.
Give the third child 1 candy.
注意事项
数据保证评级的范围是[0,2000]
public class Solution {
/**
* @param ratings: Children's ratings
* @return: the minimum candies you must give
*/
public int candy(int[] ratings) {
int[] dpL = new int[ratings.length];
int[] dpR = new int[ratings.length];
dpL[0] = 1;
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
dpL[i] = dpL[i - 1] + 1;
} else {
dpL[i] = 1;
}
}
dpR[ratings.length - 1] = 1;
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
dpR[i] = dpR[i + 1] + 1;
} else {
dpR[i] = 1;
}
}
int sum = 0;
for (int i = 0; i < ratings.length; i++) {
sum += Math.max(dpL[i], dpR[i]);
}
return sum;
}
}