Daily Temperatures

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

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

Q: Почему стек хранит индексы, а не температуры?

Ответ для дня — это расстояние, today - day , поэтому тебе нужна позиция дня. Индекс также показывает, какую ячейку массива ответов заполнить, когда день будет извлечён. До температуры всего один шаг поиска: temperatures[day] , поэтому её хранение ничего не добавляет.

Q: Можно ли решить задачу Daily Temperatures без стека?

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

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

+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, поэтому ожидание составляет 2 дня. В дни 3 и 4 температура одинаковая — 70: второй день с температурой 70 не теплее, поэтому день 3 ждёт до дня 5 с температурой 75, то есть 2 дня. После 75 или 68 более тёплых дней нет, поэтому для обоих результат — 0.

+13 скрытых тестов при отправке

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

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

Решение

Для одного дня ответом будет просмотр вперёд, но просмотр для каждого дня повторяет одну и ту же работу, а когда тёплые дни редки, каждый просмотр проходит до конца массива. Решение — позволить каждому дню давать ответ для предыдущих дней, а не спрашивать о последующих: стек индексов дней, которые ещё ждут ответа и упорядочены по температуре, позволяет получить все ответы за один проход.

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

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

Идея

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

Это правильно, потому что при проверке дни в дальнейшем идут по порядку, поэтому первый встретившийся более тёплый день и есть ближайший такой день. Важно также остановиться именно на нём: если продолжить проверку, будет записан последний более тёплый день.

Этот способ медленный, если более тёплые дни далеко или их нет. Если все 10^4 дней имеют одинаковую температуру, проверка никогда не завершится раньше времени: для дня 0 проверяются 9,999 дней, для дня 1 — 9,998, а всего получается около 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 в качестве ответа. Затем поместите сегодняшний день в стек — теперь он ждёт своего более тёплого дня.

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

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

В стеке хранятся индексы, а не температуры, потому что ответ — это расстояние, а ещё потому, что нужно знать, какую ячейку ответа заполнить. Получить температуру можно с помощью temperatures[day]. Каждый день помещается в стек один раз и извлекается не более одного раза, поэтому общее число извлечений за весь проход не превышает 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

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

В цикле со стеком всего несколько строк; ошибки скрываются в сравнении и в том, что хранится в стеке.

Удаление элементов при >= вместо >. День с такой же температурой не теплее. В [71, 69, 72, 70, 70, 75, 68] день 3 ждёт 2 дня до 75, а не 1 день до второго 70.
Добавление в стек температур вместо индексов. Ответ — это расстояние в днях, поэтому индекс нужен и для его вычисления, и чтобы знать, какую ячейку заполнить.
Использование if там, где нужен while. Один тёплый день может сразу дать ответ для многих дней ожидания: 75 в первом примере даёт ответ для трёх дней.
Возврат более высокой температуры или индекса более тёплого дня. Результат показывает, сколько дней нужно ждать: j-i.
Оставление дней, которые всё ещё находятся в стеке, без ответа. Их ответ — 0; в C выделите память для ответа с помощью calloc или заполните её, поскольку память, выделенная с помощью malloc, содержит мусор.
Продолжение прямого прохода дальше первого более тёплого дня. Без break будет записан последний более тёплый день вместо первого.

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

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

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

Почему стек хранит индексы, а не температуры?

Ответ для дня — это расстояние, today - day, поэтому тебе нужна позиция дня. Индекс также показывает, какую ячейку массива ответов заполнить, когда день будет извлечён. До температуры всего один шаг поиска: temperatures[day], поэтому её хранение ничего не добавляет.

Можно ли решить задачу Daily Temperatures без стека?

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

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

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