Сложность: hard
В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.
Вы раздаете конфеты этим детям с соблюдением следующих требований:
Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.
Пример:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
👨💻 Алгоритм:
1⃣Инициализация и первичное заполнение массивов:
Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете.
2⃣Обход и обновление значений в массивах:
Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа.
Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа.
3⃣Расчет минимального количества конфет:
Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет.
Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил.
😎 Решение:
func candy(_ ratings: [Int]) -> Int {
let len = ratings.count
var sum = 0
var left2right = Array(repeating: 1, count: len)
var right2left = Array(repeating: 1, count: len)
for i in 1..<len {
if ratings[i] > ratings[i - 1] {
left2right[i] = left2right[i - 1] + 1
}
}
for i in stride(from: len - 2, through: 0, by: -1) {
if ratings[i] > ratings[i + 1] {
right2left[i] = right2left[i + 1] + 1
}
}
for i in 0..<len {
sum += max(left2right[i], right2left[i])
}
return sum
}Ставь 👍 и забирай 📚 Базу знаний