Скользящее окно с двумя деками: максимум минус минимум на окне переменной длины
Задача: найти самый длинный подотрезок, в котором max - min <= D (разброс значений ограничен). Понимаю монотонный дек для минимума окна, но тут окно переменной длины и нужны одновременно и max, и min. Как это совместить за O(n)?
2 ответа
Держим два монотонных дека: один для максимума окна (значения убывают от головы к хвосту), другой для минимума (значения возрастают). Голова дека-max = максимум окна, голова дека-min = минимум окна. Двигаем правый указатель, расширяя окно; пока max - min > D, сужаем слева, синхронно чистя головы деков от выходящих индексов.
int longestWithin(const vector<int>& a, int D) {
deque<int> mx, mn; // индексы; mx: значения убывают, mn: возрастают
int l = 0, best = 0;
for (int r = 0; r < (int)a.size(); r++) {
while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
mx.push_back(r);
while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
mn.push_back(r);
while (a[mx.front()] - a[mn.front()] > D) { // окно невалидно — сужаем слева
l++;
if (mx.front() < l) mx.pop_front();
if (mn.front() < l) mn.pop_front();
}
best = max(best, r - l + 1);
}
return best;
}
Сложность O(n): каждый индекс добавляется и удаляется из каждого дека не больше одного раза (амортизация), плюс l монотонно растёт. Память O(n).
Ключ: два дека дают max и min окна за O(1) (головы), а сужение слева удаляет вышедшие индексы именно из голов. Условие сужения проверяем max - min > D, и левую границу двигаем, пока окно не станет валидным. Это шаблон «окно переменной длины + монотонные деки на оба экстремума».
Грабля порядка операций: сначала добавь r в оба дека, и только потом сужай слева — иначе при сужении можешь обратиться к пустому деку. И при сужении инкрементируй l, а из голов деков удаляй индексы, строго меньшие нового l (mx.front() < l). Частая ошибка — удалять из дека по значению при сужении: нельзя, дек хранит кандидатов, удаляем только реально вышедшие за левую границу индексы. Альтернатива двум декам — multiset окна (*begin() = min, *rbegin() = max), проще пишется, но O(n log n) и большая константа; деки дают чистый O(n).