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