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