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

O(n)

Храни индексы в двусторонней очереди, значения в которой убывают (или возрастают); удаляй с начала индексы, выпавшие из окна, и удаляй с конца индексы, проигравшие новому значению, тогда начало очереди всегда даёт максимум (или минимум) текущего окна.

Сигналы

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

Шаблон

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;
}

Похоже, но не то

Скользящее окно (фиксированное): Обычное фиксированное окно пересчитывает сумму за O(1) на шаг, но найти максимум/минимум окна так стоит O(k) на шаг (O(nk) итого), если пересканировать. Монотонная дек-очередь даёт максимум/минимум каждого окна за суммарный O(n), никогда не пересматривая проигравшее значение.
Монотонный стек: Монотонный стек снимает элементы только с одного конца (сверху). Здесь нужно убирать устаревшие индексы спереди по мере сдвига окна И снимать проигравшие значения сзади, а это требует обоих концов, то есть дек, а не односторонний стек.

n до 1e5 элементов, размер окна k -> O(n): каждый индекс входит и выходит из дек-очереди не более одного раза, суммарная работа линейна независимо от k.

Изучить этот паттерн