Монотонная дек-очередь (максимум/минимум окна)

Монотонная дек-очередь (максимум/минимум окна): как это работает?

Дек хранит индексы, а не значения. Индекс говорит, когда элемент выйдет из окна.

Перед вставкой нового индекса снимите сзади все индексы с меньшим значением. Они уже никогда не станут максимумом.

Положите новый индекс в конец. Значения теперь убывают от начала к концу.

Посмотрите на передний индекс. Если он выехал из окна, уберите его.

Теперь спереди лежит максимум окна. Читайте его без всякого перебора.

Каждый индекс кладётся один раз и снимается один раз. Именно это держит проход линейным.

Источники: Википедия: Двухсторонняя очередь, Документация Python (англ.): collections.deque

1. дек = [0]Окно из 3 по массиву [1, 3, -1, -3, 5]. Индекс 0 входит.
2. дек = [1]Тройка бьёт стоящую сзади единицу. Индекс 0 снимается с конца.
3. дек = [1, 2]-1 меньше, поэтому остаётся. Окно заполнено, максимум равен 3.
4. дек = [1, 2, 3]-3 снова меньше. Передний индекс всё ещё в окне.
5. дек = [4]Пятёрка бьёт всех и опустошает дек. Максимум равен 5.

function maxSlidingWindow(nums, k) {
    const deque = []; // stores indices, values decreasing
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        while (deque.length && deque[0] <= i - k) deque.shift();
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}

function maxSlidingWindow(nums: number[], k: number): number[] {
    const deque: number[] = []; // stores indices, values decreasing
    const result: number[] = [];
    for (let i = 0; i < nums.length; i++) {
        while (deque.length && deque[0] <= i - k) deque.shift();
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}

from collections import deque as dq

def max_sliding_window(nums, k):
    d = dq()  # indices, values decreasing
    result = []
    for i, x in enumerate(nums):
        while d and d[0] <= i - k:
            d.popleft()
        while d and nums[d[-1]] < x:
            d.pop()
        d.append(i)
        if i >= k - 1:
            result.append(nums[d[0]])
    return result

function maxSlidingWindow(array $nums, int $k): array {
    $deque = []; // indices, values decreasing
    $result = [];
    foreach ($nums as $i => $x) {
        while ($deque && $deque[0] <= $i - $k) array_shift($deque);
        while ($deque && $nums[end($deque)] < $x) array_pop($deque);
        $deque[] = $i;
        if ($i >= $k - 1) $result[] = $nums[$deque[0]];
    }
    return $result;
}

    public static int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>(); // indices, values decreasing
        int[] result = new int[nums.length - k + 1];
        int out = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            deque.addLast(i);
            if (i >= k - 1) result[out++] = nums[deque.peekFirst()];
        }
        return result;
    }

    public static int[] MaxSlidingWindow(int[] nums, int k) {
        var deque = new LinkedList<int>(); // indices, values decreasing
        var result = new int[nums.Length - k + 1];
        int outIndex = 0;
        for (int i = 0; i < nums.Length; i++) {
            while (deque.Count > 0 && deque.First.Value <= i - k) deque.RemoveFirst();
            while (deque.Count > 0 && nums[deque.Last.Value] < nums[i]) deque.RemoveLast();
            deque.AddLast(i);
            if (i >= k - 1) result[outIndex++] = nums[deque.First.Value];
        }
        return result;
    }

Монотонная дек-очередь (максимум/минимум окна): разбор примера

Самый длинный отрезок в пределах лимита

Найдите самый длинный отрезок, где наибольшее и наименьшее значения различаются не больше чем на лимит.

Отрезок должен быть непрерывным.

Растите переменное окно и держите два дека: для максимумов и для минимумов.

Когда два передних значения расходятся больше лимита, сужайте слева. Передний индекс убирайте, как только он устарел.

function longestSubarray(nums, limit) {
    const maxQ = []; // indices, values falling from front to back
    const minQ = []; // indices, values rising from front to back
    let left = 0;
    let best = 0;

    for (let right = 0; right < nums.length; right++) {
        while (maxQ.length && nums[maxQ[maxQ.length - 1]] <= nums[right]) maxQ.pop();
        while (minQ.length && nums[minQ[minQ.length - 1]] >= nums[right]) minQ.pop();
        maxQ.push(right);
        minQ.push(right);

        while (nums[maxQ[0]] - nums[minQ[0]] > limit) {
            if (maxQ[0] === left) maxQ.shift();
            if (minQ[0] === left) minQ.shift();
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

Монотонная дек-очередь (максимум/минимум окна): когда применять?

Паттерн «Монотонная дек-очередь (максимум/минимум окна)» нужен, когда в условии есть слова «максимум или минимум каждого окна размера k», «максимум/минимум скользящего окна» или «кратчайший подмассив с суммой не менее K». Решение на нём обычно укладывается в O(n).

• •максимум или минимум каждого окна размера k
• •максимум/минимум скользящего окна
• •кратчайший подмассив с суммой не менее K
• •нужно снимать/класть с обоих концов очереди
• •дек, двусторонняя очередь

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Монотонная дек-очередь (максимум/минимум окна): с чем путают?

Паттерн «Монотонная дек-очередь (максимум/минимум окна)» чаще всего путают с этими паттернами: Монотонный стек, Скользящее окно (фиксированный размер), Бинарная куча / очередь с приоритетом и Стек (LIFO).

• Монотонный стек (Monotonic stack): Стек снимает только с вершины. Дек снимает ещё и спереди, когда значение выходит из окна.
• Скользящее окно (фиксированный размер) (Sliding window (fixed size)): Скользящая сумма переживает вычитание. Максимум нет, ради этого дек и нужен.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Куча отдаёт максимум за log n. Она не умеет удалить элемент, только что вышедший из окна.
• Стек (LIFO) (Stack (LIFO)): Обычный стек не хранит порядка и открыт с одного конца. Оба ограничения тут мешают.

Монотонная дек-очередь (максимум/минимум окна): частые ошибки

• Хранят значения вместо индексов

  Без индекса не понять, когда элемент устарел. Кладите позицию и читайте значение по ней.

• Подрезают перед вставкой не тот конец

  Порядок здесь важен. Сначала снимите проигравших сзади, потом проверьте начало.

• Небрежно обходятся с равными значениями

  Снимать ли при равенстве, решает, какой из дубликатов выживет. Это важно, когда ответ это индекс.

• Берут кучу вместо дека

  Куча не умеет удалить элемент, только что вышедший из окна. Её удаления ленивые и стоят лишнего.

Монотонная дек-очередь (максимум/минимум окна): задачи с собеседований

Паттерн «Монотонная дек-очередь (максимум/минимум окна)» решает такие задачи с собеседований: Максимум скользящего окна, Отрезок с разбросом в пределах лимита, Кратчайший подмассив с суммой не меньше k, Прыжки VI, Сумма подпоследовательности с ограничением, Максимум значения уравнения и Минимум скользящего окна.

• Максимум скользящего окна: Чистая форма: читайте начало на каждом шаге.
• Отрезок с разбросом в пределах лимита: Два дека, по одному на каждый край.
• Кратчайший подмассив с суммой не меньше k: Префиксные суммы и возрастающий дек по ним.
• Прыжки VI: Лучший результат внутри достижимого окна.
• Сумма подпоследовательности с ограничением: То же окно, но по массиву динамики.
• Максимум значения уравнения: Окно по x с ключом y минус x.
• Минимум скользящего окна: Тот же код с перевёрнутым сравнением.

Монотонная дек-очередь (максимум/минимум окна): сложность по времени и памяти

У паттерна «Монотонная дек-очередь (максимум/минимум окна)» целевая сложность O(n).

n до 1e6 даёт O(n), ведь каждый индекс входит и выходит один раз. Память O(k) по размеру окна.