My code:
public class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
candy[0] = 1;
for (int i = 1; i < candy.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candy[i] = candy[i - 1] + 1;
}
else {
candy[i] = 1;
}
}
int total = candy[candy.length - 1];
for (int i = candy.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1]) {
candy[i] = candy[i + 1] + 1;
}
total += candy[i];
}
return total;
}
}
reference:
https://discuss.leetcode.com/topic/5243/a-simple-solution/3
Greedy.
直接看的答案。到现在也还不能很理解，为什么这么做就是最优的。
如果把孩子换成task, 对应的输入就是每个task的优先级。
糖就是时间片。一个糖就是一个时间片。
问你，最少要多少时间片，可以保证平衡。
Anyway, Good luck, Richardo! -- 09/28/2016
