Подсчёт дней до более высокой температуры

Условие

Дан массив целых чисел temps, отражающий температуры за каждый день. Требуется сформировать массив result, где result[i] — это количество дней, которое нужно подождать после i‑го дня, чтобы встретить день с более высокой температурой. Если такого дня нет, значение должно быть 0.

Пример 1: Ввод: temps = [73, 74, 75, 71, 69, 72, 76, 73] Вывод: [1, 1, 4, 2, 1, 1, 0, 0]

Ответ

Используйте монотонный стек индексов дней с ещё не найденной более высокой температурой. При потеплении извлекайте подходящие индексы и записывайте расстояние.

def daily_temperatures(temps):
    result = [0] * len(temps)
    waiting = []
    for day, temperature in enumerate(temps):
        while waiting and temps[waiting[-1]] < temperature:
            previous = waiting.pop()
            result[previous] = day - previous
        waiting.append(day)
    return result

Равная температура не считается потеплением, поэтому сравнение строгое. Неизвлечённые индексы сохраняют ответ 0. Каждый день один раз добавляется и не более одного раза удаляется из стека: время O(n), память O(n). Для массива из примера результат совпадает с [1, 1, 4, 2, 1, 1, 0, 0].