最近网上一个迪子员工的爆料引起了我的注意，说是离职了再想回去？别想了，HR已经放话：“拒绝二进宫！”🤔 除非你能让领导特批，迪子现在真的硬气起来了。
算法题：分发糖果
每个孩子至少一颗糖果。 相邻的孩子中，评分高的糖果多。
[1, 0, 2]。从最朴素的角度来看，光看评分是递增还是递减，就能决定糖果的分配。大方向有了，接下来细节问题就是——怎样用最少的糖果搞定分配？从左到右遍历，确保每个孩子比左边评分低的得到不少于 1 颗糖果。 从右到左遍历，再调整一波，确保右边评分低的糖果分布也合理。
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1); // 每人至少一颗糖果
// 从左到右：保证每个孩子比左边评分高时，糖果更多
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 从右到左：调整使右边评分低的糖果少
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// 计算总糖果数
int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
Math.max 确保分配的合理性。总时间复杂度是 O(n)，空间复杂度也是 O(n)。要是想再节省点内存，可以试试用变量代替数组存储，但那样代码可能没这么直观了。输入 [1, 0, 2]，输出是5。分配结果：[2, 1, 2]。输入 [1, 2, 2]，输出是4。分配结果：[1, 2, 1]。
[1, 1, 1]，那就每人 1 颗糖果，这种情况根本不用动脑子。对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
