Раздача конфет по рейтингам
Hard
Есть дети в ряд с рейтингами
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
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!