Очередь и дек

Для массива [1,-2,3,-4] и окна длины 2 дек индексов отрицательных меняется так: [] → [1] → [1] → [3]; ответы трёх окон — [-2,-2,-4].

Очередь сохраняет порядок обнаружения

Очередь работает по правилу FIFO — first in, first out. Новое значение приходит в хвост, старейшее уходит из головы. Это естественная модель для заявок, событий и BFS: вершины обрабатываются в том порядке, в котором были впервые обнаружены.

Дек (double-ended queue) разрешает добавление и удаление с обоих концов. Очередь можно представить как ограниченный интерфейс дека: push_back/append в хвост и pop_front/popleft из головы.

Почему указатель головы лучше удаления начала массива

Если после каждого извлечения физически сдвигать все элементы влево, одна операция стоит O(n). Простая очередь на массиве может хранить индекс головы и только увеличивать его. Чтобы переиспользовать освободившиеся позиции в буфере фиксированного размера, индексы головы и хвоста двигают по кругу — это модель кольцевого буфера.

Промышленные деки могут использовать кольцевой буфер или блоки памяти; конкретная деталь зависит от реализации. Для выбора алгоритма важен контракт: операции на поддерживаемых концах занимают O(1) без линейного сдвига.

В C++ std::queue даёт FIFO-интерфейс, а std::deque открывает оба конца. В Python используйте collections.deque; list.pop(0) сдвигает оставшиеся ссылки и потому не подходит для длинной очереди.

Как найти первый отрицательный элемент каждого окна?

Для каждого окна длины k вернуть первый отрицательный элемент или 0, если отрицательных нет.

Пересканирование каждого окна слева направо

Для каждого начала окна просматривать его k элементов слева направо до первого отрицательного.

Почему соседние окна повторяют одну работу?

Соседние окна почти совпадают, но перебор повторяет до k проверок; итог O(nk).

Достаточно помнить индексы отрицательных чисел

Нужно помнить только индексы отрицательных чисел. Первый из них — ответ, а вышедшие за левую границу удаляются спереди.

Какие индексы обязаны оставаться в деке?

Дек содержит возрастающие индексы всех отрицательных элементов текущего окна; передний индекс — самый ранний.

Как сдвигать окно и очищать оба конца?

При движении right добавить его индекс, если значение отрицательно. Когда сформировано окно, удалить спереди индексы меньше left, записать значение по front или 0.

Дек индексов на C++17 и Python 3

C++17

#include <deque>
#include <cassert>
#include <stdexcept>
#include <vector>
using namespace std;

vector<int> firstNegative(const vector<int>& values, int k) {
    if (k <= 0 || k > static_cast<int>(values.size())) {
        throw invalid_argument("bad window");
    }
    deque<int> negative;
    vector<int> answer;
    for (int right = 0; right < static_cast<int>(values.size()); ++right) {
        if (values[right] < 0) negative.push_back(right);
        int left = right - k + 1;
        if (left < 0) continue;
        while (!negative.empty() && negative.front() < left) {
            negative.pop_front();
        }
        answer.push_back(negative.empty() ? 0 : values[negative.front()]);
    }
    return answer;
}

int main() {
    assert((firstNegative({1, -2, 3, -4}, 2) == vector<int>{-2, -2, -4}));
    assert((firstNegative({1, 2}, 2) == vector<int>{0}));
}

Python 3

from collections import deque


def first_negative(values: list[int], k: int) -> list[int]:
    if k <= 0 or k > len(values):
        raise ValueError("bad window")
    negative: deque[int] = deque()
    answer: list[int] = []
    for right, value in enumerate(values):
        if value < 0:
            negative.append(right)
        left = right - k + 1
        if left < 0:
            continue
        while negative and negative[0] < left:
            negative.popleft()
        answer.append(0 if not negative else values[negative[0]])
    return answer


assert first_negative([1, -2, 3, -4], 2) == [-2, -2, -4]
assert first_negative([1, 2], 2) == [0]

Почему каждый индекс добавляется и удаляется один раз?

O(n) времени и O(k) памяти: каждый индекс добавляется и удаляется не более одного раза.

Очередь, дек и куча отвечают на разные вопросы

• очередь: кто пришёл раньше всех;
• дек: кто находится на одном из двух концов;
• куча: у кого сейчас минимальный или максимальный приоритет;
• стек: кто пришёл последним.

В BFS именно FIFO гарантирует обработку невзвешенного графа слоями расстояния. В скользящем окне дек хранит ещё актуальные индексы и позволяет выбрасывать устаревшие слева. В монотонном деке второй конец нужен, чтобы удалять доминируемых кандидатов.

Некорректный размер окна и отсутствие кандидата

k=1; k=n; окно без отрицательных; все значения отрицательны; k вне диапазона считается ошибкой.

Тесты на выпадение индекса из окна

[1,-2,3,-4],2 -> [-2,-2,-4], [1,2],2 -> [0], [-1],1 -> [-1], недопустимый k.

Как узнать задачу на очередь актуальных кандидатов?

Нужно сохранять порядок поступления кандидатов и удалять устаревшие элементы с начала.

Когда нужно хранить всё окно, а не его первый элемент?

Если нужен только доступ к одному концу по LIFO, достаточно стека; если кандидаты имеют приоритет, нужна куча. Дек не даёт быстрого поиска произвольного значения и не заменяет хеш-множество. Очередь также не подходит для взвешенного кратчайшего пути, где следующим должен стать не самый ранний, а самый дешёвый кандидат.

Мини-проверка: зачем хранить именно индексы?

Вопрос: зачем хранить индексы, а не значения? Ответ: индекс позволяет понять, вышел ли кандидат из окна.

Мини-проверка: когда удаляется front?

Вопрос: может ли один индекс удалиться дважды? Ответ: нет; после pop_front он навсегда покидает дек, поэтому суммарная работа линейна.

Проведите дек через три соседних окна

Для [2,-1,-3,4,-2], k=3 выпишите дек индексов и ответ после каждого завершённого окна.

Найдите ответы для окон без подсказки

Задача 1

Для каждого окна длины k верните индекс первого чётного элемента или -1; недопустимый k должен отклоняться.

Дек избавляет соседние окна от повторного просмотра

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