5407. Раздача конфет по рейтингам
Hard
1 решил
Есть дети в ряд с рейтингами
1) каждый ребёнок получает хотя бы одну конфету;
2) если рейтинг ребёнка строго выше, чем у соседа слева или справа, у него должно быть строго больше конфет, чем у этого соседа.
При равных рейтингах строгое неравенство по конфетам не требуется. Нужно минимизировать суммарное число конфет и вернуть эту сумму.
ratings. Раздайте конфеты по правилам:1) каждый ребёнок получает хотя бы одну конфету;
2) если рейтинг ребёнка строго выше, чем у соседа слева или справа, у него должно быть строго больше конфет, чем у этого соседа.
При равных рейтингах строгое неравенство по конфетам не требуется. Нужно минимизировать суммарное число конфет и вернуть эту сумму.
Примеры:
Вход:
[1, 0, 2]
Выход:
5
Объяснение: [1,0,2]: среднему с рейтингом 0 достаточно 1 конфеты; соседям с более высоким рейтингом — по 2. Раздача [2,1,2], сумма 5.
Вход:
[1, 2, 2]
Выход:
4
Объяснение: [1,2,2]: можно раздать [1,2,1]. У двух последних рейтинги равны, поэтому у них может быть разное или одинаковое число конфет — строгого требования нет. Сумма 4.
Вход:
[1]
Выход:
1
Объяснение: [1]: один ребёнок получает минимум — 1 конфету.
Ограничения:
1 <= ratings.length <= 2*10^4
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!