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