Sliding Window Maximum

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

+10

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

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

Функция

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

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

Ограничения

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

Примеры

Ввод: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Вывод: [12, 12, 12, 8, 8]
Пояснение: 12 находится в первых трёх окнах: [4, 2, 12], [2, 12, 3] и [12, 3, 8]. После того как оно выходит из окна, в окнах [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 не добавляет второй ответ.

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

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Самая очевидная идея следует из формулировки. Окно, начинающееся с индекса start, охватывает элементы от start до start+k-1. Прочитайте эти k значений, сохраните наибольшее и сдвиньте начало на одну позицию вправо. Всего есть n-k+1 начальных позиций — от 0 до n-k.

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

Алгоритм медленный. Для каждого из n-k+1 окон требуется k чтений, а произведение максимально, когда k примерно равно половине n. При n = 2 × 10^4 и k = 10^4 получается 10^4 окон по 10^4 значений, то есть 10^8 чтений. Хуже того, у двух соседних окон k-1 общих значений, поэтому почти каждое чтение повторяет то, что вы уже прочитали.

Алгоритм

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

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 и так далее; последний блок будет короче, если n не кратно k. Окно имеет длину ровно k, поэтому оно либо совпадает с одним блоком, либо захватывает конец одного блока и начало следующего. Оно никогда не затрагивает три блока.

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

Для nums = [4, 2, 12, 3, 8, 5, 1] и k = 3 блоки будут такими: [4, 2, 12], [3, 8, 5] и [1]. fromStart — это [4, 4, 12, 3, 8, 8, 1], а toEnd — [12, 12, 12, 8, 8, 5, 1]. Окно [2, 12, 3] начинается с индекса 1: toEnd[1] = 12 охватывает 2 и 12, fromStart[3] = 3 охватывает 3, и результат равен 12.

Алгоритм работает за время O(n), выполняя три прохода по массиву. Понадобятся два вспомогательных массива длины n, а чтобы ответить для первого окна, сначала нужен весь исходный массив.

Алгоритм

Заполните fromStart слева направо: скопируйте nums[i], если i кратно k, иначе возьмите большее из fromStart[i-1] и nums[i].
Заполните toEnd справа налево: скопируйте nums[i], если i — последний индекс или i+1 кратно k, иначе возьмите большее из toEnd[i+1] и nums[i].
Для каждого начального индекса 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, содержит и i, потому что i находится правее и покидает окно позже. Во всех таких окнах nums[i] не меньше, поэтому j уже никогда не сможет стать максимумом. Как только появляется i, j становится бесполезным, и о нём можно забыть.

Храни в двусторонней очереди индексы, о которых ты ещё не забыл. Когда появляется i, удаляй индексы с конца, пока их значения не станут меньше или равны nums[i], а затем добавь i. Оставшиеся значения будут строго убывать спереди назад, потому что любой более старый элемент, который не был больше, уже удалили бы. Поэтому в начале очереди находится наибольшее значение в окне. Дек хранит индексы, а не значения, потому что элемент в начале тоже должен удаляться, когда окно проходит через него: окно, которое заканчивается на i, начинается с i-k+1, поэтому индекс i-k уже вышел из окна, и, если он находится в начале очереди, его нужно удалить.

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

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

Алгоритм

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

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

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

Большинство ошибок связано с границами окна или с тем, что хранится в деке.

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

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

Какова временная сложность задачи «Максимум в скользящем окне»?

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

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

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

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

Передний элемент должен покинуть очередь, когда окно сдвигается за него, и только его индекс подскажет тебе об этом. По одним значениям пришлось бы угадывать по nums[i-k], что не сработает, если одно и то же значение встречается больше одного раза. Индекс также позволяет получить значение без дополнительных затрат: nums[index].

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

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

Python

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

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

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

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

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

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