Sliding Window Maximum

СложноСкользящее окно Монотонный стек Очередь

+10

Дан массив целых чисел nums и размер окна k. Окно из k последовательных значений начинается с левого края и каждый раз сдвигается вправо на одну позицию, пока его правый край не окажется на последнем значении. Верните наибольшее значение в окне для каждой позиции, слева направо: n-k+1 значений для массива длины n.

Функция

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: массив, по которому скользит окно
kinteger: количество значений в каждом окне
Возвращаетinteger-array: наибольшее значение каждого окна, от самого левого окна до самого правого

Ограничения

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
The result содержит nums.length-k+1 значений — по одному на окно, в порядке слева направо.

Примеры

Ввод: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Вывод: [12, 12, 12, 8, 8]
Пояснение: 12 входит в первые три окна, поэтому каждое из них отвечает 12. После того как он выйдет из окна, [3, 8, 5] и [8, 5, 1] имеют наибольшее значение 8.

Ввод: nums = [-3, -1, -7, -2]k = 2
Вывод: [-1, -1, -2]
Пояснение: Окна — это [-3, -1], [-1, -7] и [-7, -2]. Наибольшее из двух отрицательных чисел — то, которое ближе к нулю, поэтому получаем -1, -1 и -2.

Ввод: nums = [6, 6, 1]k = 3
Вывод: [6]
Пояснение: Когда k равно длине массива, есть одно окно — весь массив. Его наибольшее значение — 6; вторая копия 6 не добавляет второго ответа.

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

Сможешь создать очередь, которая позволяет добавлять значение в конец, удалять значение из начала и считывать её текущее максимальное значение — всё это за амортизированное время O(1)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Соседние окна имеют k-1 общих значений, поэтому при повторном вычислении каждого максимума почти вся работа выполняется заново. Но отменить максимум нельзя: когда наибольшее значение выходит из окна, нужно найти следующее по величине, не просматривая окно заново. Монотонная дека хранит только значения, которые ещё могут стать максимумом; ответ находится в её начале.

Просканируйте каждое окно

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

Идея

Считай значения k в каждом окне и сохраняй наибольшее. Каждое окно считывается полностью, поэтому его максимум невозможно пропустить. Для каждого из n-k+1 окон требуется k операций чтения; в худшем случае k составляет примерно половину от n: при n = 2 × 10^4 и k = 10^4 получается около 10^4 окон по 10^4 значений, то есть 10^8 операций чтения.

Алгоритм

Перебирай start от 0 до n-k.
Найди наибольшее значение среди элементов от nums[start] до nums[start+k-1].
Добавь его в результат и верни результат после цикла.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

Блоки с максимумами с каждой стороны

Идея

Разбейте массив на блоки длины k: индексы от 0 до k-1, затем от k до 2k-1 и так далее; если k не делит n, последний блок будет короче. Окно имеет длину ровно k, поэтому оно представляет собой либо один целый блок, либо конец одного блока и начало следующего.

Заранее вычислите fromStart[i] — наибольшее значение от начала блока, которому принадлежит i, до i, — и toEnd[i] — наибольшее значение от i до конца его блока. Окно, начинающееся с i, заканчивается на i+k-1: toEnd[i] охватывает его левую часть, а fromStart[i+k-1] — правую, поэтому большее из этих значений и есть максимум окна. В первом примере для окна [2, 12, 3] берутся toEnd[1] = 12 и fromStart[3] = 3, что даёт 12.

Три прохода обеспечивают время работы O(n) ценой двух вспомогательных массивов длины n и необходимости иметь весь массив до получения первого ответа.

Алгоритм

Заполняйте fromStart слева направо, начиная заново с nums[i], когда i кратно k.
Заполняйте toEnd справа налево, начиная заново с nums[i] на последнем индексе и везде, где i+1 кратно k.
Для каждого начала i от 0 до n-k добавьте большее из значений toEnd[i] и fromStart[i+k-1].

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

Монотонная дека индексов

Идея

Если индекс j стоит раньше i и nums[j] ≤ nums[i], то j уже никогда не сможет быть максимумом: каждое последующее окно, в котором есть j, содержит и i, который покидает окно позже. Поэтому, когда появляется i, можно забыть о j.

Храни в деке индексы, о которых ещё не забыли. Когда появляется i, извлекай с конца индексы, значения которых не больше nums[i], а затем добавляй i. Значения оставшихся индексов строго убывают от начала к концу, поэтому первый элемент — максимум в окне. Храни индексы, потому что первый элемент тоже должен покинуть дек, когда окно пройдёт через него. В первом примере на индексе 5 в деке находятся 12, 8 и 5; 12 находится по индексу 5 - 3 = 2, поэтому он покидает дек, а ответ — 8.

Каждый индекс добавляется один раз и извлекается не более одного раза: всего не более 2n операций с деком, время работы — O(n). В деке никогда не бывает больше k индексов.

Алгоритм

Для каждого индекса i извлекайте индексы с конца, пока дека не пуста и значение в её конце не меньше nums[i].
Добавьте i в конец.
Если индекс в начале равен i-k, он покинул окно: извлеките его.
Когда i ≥ k-1, добавьте значение по индексу в начале в результат.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

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

Хранение значений вместо индексов. Для [3, 1, 3] и k = 2 вторая 3 удаляет первую из дека, а затем сама удаляется, потому что равна nums[0] — значению, которое вышло из окна.
Слишком ранний или слишком поздний вывод ответа. Первое полное окно заканчивается на индексе k-1, а результат должен содержать ровно n-k+1 значений.
Удаление i-k+1 вместо i-k. Этот индекс всё ещё соответствует первому значению окна.
Чтение последнего элемента дека без проверки, что в нём что-то есть.
В блочном подходе важно не забыть, что последний блок может быть короче k. При проходе справа налево нужно начинать заново и с последнего индекса, и в конце каждого блока.

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

Какова временная сложность алгоритма нахождения максимума в скользящем окне?

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

Можно ли решить задачу о максимуме скользящего окна с помощью кучи?

Да. Помещайте пары из значения и индекса в max-кучу, а перед чтением верхнего элемента извлекайте его, пока его индекс находится за пределами окна. Это занимает время O(n log n) и может хранить до n элементов. Дек работает быстрее и занимает меньше места, потому что удаляет бесполезные значения сразу, как только появляется большее.

В чём разница между монотонной декой и монотонным стеком?

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

def maxSlidingWindow(nums, k):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

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

[12, 12, 12, 8, 8]

Sliding Window Maximum

Функция

Ограничения

Примеры

Подсказки

Решение

Просканируйте каждое окно

Блоки с максимумами с каждой стороны

Монотонная дека индексов

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

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

Похожие задачи