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

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

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

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

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

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

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

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

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 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
• •нужно снимать/класть с обоих концов очереди
• •дек, двусторонняя очередь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O(n)

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