Candy

Сложная№135два прохода

Дети стоят в ряд, у каждого есть оценка. Раздайте им конфеты: каждому хотя бы одну, а ребёнку с оценкой выше, чем у соседа, — больше, чем этому соседу. Найдите наименьшее число конфет всего. Наш пример: [2, 4, 3, 5, 2, 1, 1, 3] — ответ 13: [1, 2, 1, 3, 2, 1, 1, 2].

135 CandyРазбор · 1×

Пример: [2, 4, 3, 5, 2, 1, 1, 3]. Верхний ряд — оценки, дуга сравнивает i с соседом; нижний ряд — конфеты.

оценки0214233542516173конфеты
ребёнок iсосед, с которым сравниваемконфеты на сейчасконфеты только что изменились

8 детей в ряд

01/37
сначала · назад · пуск · шаг
Скорость
1function candy(ratings):
2 n = len(ratings)
3 candies = [1] * n
4 for i from 1 to n - 1:
5 if ratings[i] > ratings[i - 1]:
6 candies[i] = candies[i - 1] + 1
7 for i from n - 2 down to 0:
8 if ratings[i] > ratings[i + 1]:
9 candies[i] = max(candies[i], candies[i + 1] + 1)
10 return sum(candies)
состояние
n
8
i
–
candies
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У правила две стороны, и каждый проход закрывает одну. Слева направо каждый ребёнок получает наименьшее число конфет, которое устраивает соседа слева, с учётом того, сколько уже у соседа.
  2. Справа налево max(candies[i], candies[i + 1] + 1) добавляет правую сторону, не ломая левую: число конфет только растёт, а рост не мешает ребёнку, которому положено больше, чем соседу слева.
  3. Каждое число — длина самого длинного подъёма оценок, который кончается на этом ребёнке, слева или справа, какой длиннее; никакая правильная раздача не даст меньше.

Сложность

Время O(n): два прохода по ряду. Память O(n) на конфеты.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.