ML Mentor

Раздача конфет

HardАлгоритмы
10:00
Лучше работает на десктопе
GreedyArrays

N детей стоят в ряду. У каждого есть рейтинг ratings[i]. Нужно раздать конфеты по правилам:

  1. Каждый ребёнок получает хотя бы 1 конфету.
  2. Ребёнок с более высоким рейтингом получает больше конфет, чем его сосед(и) с меньшим рейтингом.

Верните минимальное общее количество конфет.

Сигнатура

def candy(ratings: list[int]) -> int:

Constraints

  • 1 ≤ len(ratings) ≤ 2 × 10⁴
  • 0 ≤ ratings[i] ≤ 2 × 10⁴

Примеры

Пример 1

Вход:
ratings = [1,0,2]
Выход:5

Пример 2

Вход:
ratings = [1,2,2]
Выход:4

Пример 3

Вход:
ratings = [1,3,2,2,1]
Выход:7
Консоль
Нажмите Run или Ctrl+Enter для запуска