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