Daily Temperatures (Ожидание потепления)
Описание: Дан массив дневных температур. Для каждого дня верните, через сколько дней станет теплее. Если потепления не будет, поставьте 0.
Пример 1:
Вход: temperatures = [73,74,75,71,69,72,76,73]
Выход: [1,1,4,2,1,1,0,0]
Объяснение: Для дня 0 потепление наступит уже завтра
Пример 2:
Вход: temperatures = [30,40,50,60]
Выход: [1,1,1,0]
Объяснение: Каждый день теплее предыдущего
Ограничения:
1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100
Рекомендуемая временная и пространственная сложность
Стремитесь к O(n) по времени и O(n) по памяти.
Подсказка 1
Перебор всех пар даёт O(n²). Можно ли за один проход?
Подсказка 2
Храните в стеке индексы дней, для которых ответ ещё не найден.
Подсказка 3
Когда пришёл день теплее вершины стека — вы нашли ответ для неё. Снимайте, пока текущая температура больше.