135. Candy
有 n 個孩子站成一排。每個孩子被分配了一個在整數數組 ratings 中給出的評分值。
你需要給這些孩子分配糖果，並滿足以下要求：每個孩子至少要有一顆糖果。
評分較高的孩子比他們的鄰居得到更多的糖果。
返回你需要分配的糖果的最少數量。
範例：
輸入：ratings = [1,0,2] 輸出：5 解釋：你可以分別給第一個、第二個和第三個孩子分配 2、1、2 顆糖果。
Python
from typing import List
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
if n == 0:
return 0
# Initialize candies array with 1 candy for each child
candies = [1] * n
# Left to right pass to ensure higher ratings get more candies than the left neighbor
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# Right to left pass to ensure higher ratings get more candies than the right neighbor
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
# The total number of candies needed
return sum(candies)
19.04MB, 129ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
if (n == 0) return 0;
// Initialize candies array with 1 candy for each child
vector<int> candies(n, 1);
// Left to right pass to ensure higher ratings get more candies than the left neighbor
for (int i = 1; i < n; ++i) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Right to left pass to ensure higher ratings get more candies than the right neighbor
for (int i = n - 2; i >= 0; --i) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = max(candies[i], candies[i + 1] + 1);
}
}
// The total number of candies needed
int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
};
20.03MB, 16ms
Javascript
/**
* @param {number[]} ratings
* @return {number}
*/
var candy = function(ratings) {
const n = ratings.length;
if (n === 0) return 0;
// Initialize candies array with 1 candy for each child
const candies = new Array(n).fill(1);
// Left to right pass to ensure higher ratings get more candies than the left neighbor
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Right to left pass to ensure higher ratings get more candies than the right neighbor
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// The total number of candies needed
return candies.reduce((total, num) => total + num, 0);
};
53.22MB, 63ms
