Почему это работает
- Клетки до end — ровно те, до которых можно дойти за jumps прыжков, а клетки после end до far требуют ещё одного. Проход идёт по массиву отрезок за отрезком, как поиск в ширину, только без очереди.
- Из какой клетки будет следующий прыжок, решается только когда i дошёл до end: к этому моменту все клетки отрезка уже просмотрены, и far — самый дальний из их прыжков. Ничего не выбирается раньше, чем известны все варианты.
- Цикл кончается до последнего индекса: встать на него — значит дойти, а прыжок оттуда добавил бы лишний.
Сложность
Время O(n): один проход по массиву. Память O(1): только jumps, end и far.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗