当前位置： 面试刷题>> 分发糖果(经典算法150题)
### 题目描述
**分发糖果**
在一所小学里，老师准备了一些糖果要分发给班上的学生。为了公平起见，老师决定根据每个学生的表现来分配糖果数量。规则如下：
1. **相邻规则**：如果某个学生A的表现比相邻的学生B好，那么学生A应该得到比学生B更多的糖果。
2. **从左到右遍历**：首先从左到右遍历学生，确保每个学生至少得到比左边学生多的糖果（如果左边有学生且表现不如他）。
3. **从右到左遍历**：然后再从右到左遍历，确保每个学生得到的糖果数量也满足比右边学生多（如果右边有学生且表现不如他）的条件。
给定一个数组`ratings`，其中`ratings[i]`代表第`i`个学生的表现评分。请编写一个函数`distributeCandies`来计算并返回老师至少需要准备的糖果总数，以满足上述规则。
### 示例
输入：`ratings = [1, 0, 2]`
输出：5
解释：第一个学生得到1个糖果，第二个学生得到0个糖果，第三个学生得到4个糖果，因为第二个学生的评分低于其他两个学生。
### PHP 代码示例
```php
function distributeCandies($ratings) {
$n = count($ratings);
$candies = array_fill(0, $n, 1); // 每个学生至少有一个糖果
// 从左到右遍历
for ($i = 1; $i < $n; $i++) {
if ($ratings[$i] > $ratings[$i - 1]) {
$candies[$i] = $candies[$i - 1] + 1;
}
}
// 从右到左遍历
for ($i = $n - 2; $i >= 0; $i--) {
if ($ratings[$i] > $ratings[$i + 1] && $candies[$i] <= $candies[$i + 1]) {
$candies[$i] = $candies[$i + 1] + 1;
}
}
// 计算总糖果数
return array_sum($candies);
}
// 示例用法
$ratings = [1, 0, 2];
echo distributeCandies($ratings); // 输出 5
```
### Python 代码示例
```python
def distributeCandies(ratings):
n = len(ratings)
candies = [1] * n # 每个学生至少有一个糖果
# 从左到右遍历
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# 从右到左遍历
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
candies[i] = candies[i + 1] + 1
# 计算总糖果数
return sum(candies)
# 示例用法
ratings = [1, 0, 2]
print(distributeCandies(ratings)) # 输出 5
```
### JavaScript 代码示例
```javascript
function distributeCandies(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1); // 每个学生至少有一个糖果
// 从左到右遍历
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 从右到左遍历
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
}
}
// 计算总糖果数
return candies.reduce((sum, candy) => sum + candy, 0);
}
// 示例用法
const ratings = [1, 0, 2];
console.log(distributeCandies(ratings)); // 输出 5
```
以上代码实现了分发糖果的算法，并符合题目要求。这些代码示例可以在实际面试或算法练习中使用，并可根据需要进行调整和优化。