Daily Temperatures

Q: Какова временная сложность задачи Daily Temperatures?

Решение с монотонным стеком работает за время O(n) и использует O(n) дополнительной памяти, потому что каждый день добавляется в стек один раз и удаляется из него не более одного раза. Просмотр вперёд от каждого дня занимает O(n²) времени — около 5 × 10^7 сравнений для 10^4 дней, для которых нет более тёплого дня.

СреднеМонотонный стек

+10

temperatures[i] — это температура в день i. Для каждого дня подсчитай, сколько дней нужно ждать после него, пока не наступит строго более тёплый день, или укажи 0, если позже более тёплого дня не будет. Верни массив той же длины, в котором элемент i — это время ожидания для дня i.

Функция

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: температура каждого дня по порядку
Возвращаетinteger-array: для каждого дня — количество дней до более тёплого дня или 0, если такого дня не будет

Ограничения

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
«Теплее» означает строго более высокую температуру: более поздний день с такой же температурой не считается.

Примеры

Ввод: temperatures = [71, 69, 72, 70, 70, 75, 68]
Вывод: [2, 1, 3, 2, 1, 0, 0]
Пояснение: День 0 (71) ждёт 2 дня, пока температура не достигнет 72. День 3 (70) пропускает равную температуру 70 в день 4 и ждёт 2 дня, пока температура не достигнет 75. После 75 или 68 уже нет более высокой температуры, поэтому оба значения получают 0.

Дополнительный вопрос

Температура принимает всего 71 значение: от 30 до 100. Как таблица с индексами по температуре могла бы за один проход ответить на запросы для каждого дня, двигаясь справа налево, и какой ценой?

Решение

Прямой просмотр от каждого дня повторяет работу, а когда тёплые дни редки, каждый просмотр доходит до конца. Вместо этого пройди по дням один раз и позволь каждому новому дню ответить на те предыдущие дни, которые он превосходит. Дни, которые всё ещё ждут ответа, находятся в стеке, температуры в котором не возрастают снизу вверх, поэтому все ответы находятся за один проход.

Просматривайте вперёд от каждого дня

Верно, но не успевает на самых больших тестах

Идея

Для дня i проверь дни i+1, i+2 и так далее, остановившись на первом дне j со строго более высокой температурой. Ответ — j-i или 0, если просмотр дошёл до конца. Просмотр по порядку гарантирует, что первый встретившийся более тёплый день будет самым ранним.

Если температура во все 10^4 дней одинаковая, просмотр не остановится раньше времени: около n²/2 = 5 × 10^7 сравнений, а день 1 проходит почти тот же путь, что день 0 уже прошёл.

Алгоритм

Создай массив ответов из нулей, по одному элементу на каждый день.
Для каждого дня i просматривай j от i+1 до последнего дня.
При первом j, для которого temperatures[j] > temperatures[i], сохрани j-i и останови просмотр.
Верни массив ответов; для дней, при просмотре которых ничего не нашлось, оставь 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Монотонный стек дней ожидания

Идея

Храни дни, для которых пока нет ответа, в стеке в виде индексов. Когда наступает сегодняшний день, извлекай из стека все ожидающие дни с более низкой температурой: для них сегодняшний день — первый более тёплый, поэтому ответ — today - day. Затем добавь в стек сегодняшний день.

Проверять нужно только верхний элемент. День добавляется в стек лишь после того, как все более холодные дни над ним были извлечены, поэтому температуры в стеке не возрастают снизу вверх. Если сегодня не теплее верхнего элемента, то оно не теплее ни одного дня ниже, и извлечение прекращается. В первом примере день 5 (75) извлекает дни 4, 3 и 2 с ожиданием 1, 2 и 3 дня соответственно, а второй день с температурой 70 так и не извлёк первый, поскольку равная температура не считается более тёплой.

Каждый день добавляется в стек один раз и извлекается не более одного раза, поэтому общее число извлечений не превышает n: время работы — O(n), хотя один день может привести к извлечению многих дней.

Алгоритм

Создайте массив ответов, заполненный нулями, и пустой стек индексов.
Для каждого дня today, пока день на вершине стека холоднее, чем сегодня, извлеките его из стека и установите для него ответ, равный today минус его индекс.
Добавьте today в стек.
После цикла у дней, которые остались в стеке, нет более тёплого дня, поэтому для них остаётся 0. Верните массив ответов.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

Ловушки и крайние случаи

Удаление из стека при >= вместо >. В первом примере день 3 тогда ждет 1 день до второго 70 вместо 2 дней до 75.
Добавление в стек температур вместо индексов. Тогда нельзя вычислить расстояние или определить, какую ячейку ответа заполнить.
Использование if там, где нужен while. Один теплый день может дать ответ сразу для многих дней ожидания: 75 в первом примере дает ответ для трех дней.
Оставление дней, которые все еще находятся в стеке, без заданного ответа. Их ответ равен 0; в C выделяй память для массива ответов с помощью calloc, потому что память, выделенная с помощью malloc, содержит мусор.
Продолжение прямого прохода после первого более теплого дня. Без break вместо него записывается последний более теплый день.

Частые вопросы3

Какова временная сложность задачи Daily Temperatures?

Решение с монотонным стеком работает за время O(n) и использует O(n) дополнительной памяти, потому что каждый день добавляется в стек один раз и удаляется из него не более одного раза. Просмотр вперёд от каждого дня занимает O(n²) времени — около 5 × 10^7 сравнений для 10^4 дней, для которых нет более тёплого дня.

Можно ли решить задачу «Ежедневные температуры» без стека?

Да. Заполняйте ответы, двигаясь от последнего дня назад, и для дня i начинайте с j = i+1; пока день j не теплее, переходите к j + answer[j] — дню, который отвечает на вопрос для j. Если answer[j] равно 0, то и для дня i ответ будет 0. Такие переходы пропускают дни, которые не могут дать ответ для i: время O(n), дополнительная память не нужна.

Как задача о ежедневных температурах связана с задачей о следующем большем элементе?

Для каждой позиции задаётся один и тот же вопрос: найди следующее большее значение справа. Next Greater Element возвращает это значение; Daily Temperatures возвращает расстояние до него, поэтому стек хранит индексы. Тот же стек, настроенный на извлечение при меньшем значении, отвечает на вопросы о следующем меньшем элементе.

def dailyTemperatures(temperatures):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

temperatures = [71, 69, 72, 70, 70, 75, 68]

Ожидаемый вывод

[2, 1, 3, 2, 1, 0, 0]