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