Монотонный стек и монотонный дек

В [2,1,4] индексы 0 и 1 ждут большего справа; значение 4 снимает сначала 1, затем 2 и записывает ответ 4 для обоих, а само остаётся без ответа.

Как найти ближайший больший элемент справа?

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

Поиск ответа в каждом суффиксе

Для каждой позиции сканировать суффикс до первого большего элемента.

Почему один суффикс просматривается много раз?

Один и тот же суффикс пересматривается для многих позиций, что даёт O(n²).

Когда текущий элемент становится окончательным ответом?

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

Какой порядок поддерживает стек индексов?

Стек содержит индексы без найденного ответа, а их значения идут невозрастающе снизу вверх.

Снимаем кандидатов, которых вытеснило новое значение

Идти слева направо. Пока values[i] > values[stack.top], записывать текущий элемент как ответ и снимать индекс. Затем положить i. Оставшимся ответ остаётся -1.

Когда одного конца уже недостаточно

Для максимума каждого окна длины k кандидат может потерять полезность по двум разным причинам:

1. его вытеснило справа не меньшее значение — такой индекс удаляется с конца дека;
2. его индекс вышел за левую границу окна — он удаляется с начала.

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

Для [1,3,-1,-3,5] и k=3 индекс 1 со значением 3 остаётся первым для окон [1,3,-1] и [3,-1,-3], затем выходит по позиции. При добавлении 5 все меньшие значения с конца удаляются, и 5 становится новым максимумом.

Монотонный стек на C++17 и Python 3

C++17

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

vector<int> nextGreater(const vector<int>& values) {
    vector<int> answer(values.size(), -1);
    stack<int> pending;
    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        while (!pending.empty() && values[i] > values[pending.top()]) {
            answer[pending.top()] = values[i];
            pending.pop();
        }
        pending.push(i);
    }
    return answer;
}

vector<int> slidingWindowMaximum(const vector<int>& values, int window) {
    if (window <= 0 || window > static_cast<int>(values.size())) {
        throw invalid_argument("invalid window size");
    }
    deque<int> candidates;
    vector<int> answer;
    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        while (!candidates.empty() && candidates.front() <= i - window) {
            candidates.pop_front();
        }
        while (!candidates.empty() && values[candidates.back()] <= values[i]) {
            candidates.pop_back();
        }
        candidates.push_back(i);
        if (i + 1 >= window) answer.push_back(values[candidates.front()]);
    }
    return answer;
}

int main() {
    assert((nextGreater({2, 1, 2, 4, 3}) == vector<int>{4, 2, 4, -1, -1}));
    assert((nextGreater({3, 2, 1}) == vector<int>{-1, -1, -1}));
    assert((slidingWindowMaximum({1, 3, -1, -3, 5, 3, 6, 7}, 3) ==
            vector<int>{3, 3, 5, 5, 6, 7}));
}

Python 3

from collections import deque


def next_greater(values: list[int]) -> list[int]:
    answer = [-1] * len(values)
    pending: list[int] = []
    for index, value in enumerate(values):
        while pending and value > values[pending[-1]]:
            answer[pending.pop()] = value
        pending.append(index)
    return answer


def sliding_window_maximum(values: list[int], window: int) -> list[int]:
    if not 1 <= window <= len(values):
        raise ValueError("invalid window size")
    candidates: deque[int] = deque()
    answer: list[int] = []
    for index, value in enumerate(values):
        while candidates and candidates[0] <= index - window:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(index)
        if index + 1 >= window:
            answer.append(values[candidates[0]])
    return answer


assert next_greater([2, 1, 2, 4, 3]) == [4, 2, 4, -1, -1]
assert next_greater([3, 2, 1]) == [-1, -1, -1]
assert sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]

Откуда берётся линейная амортизированная оценка?

Обе техники работают за O(n) времени: каждый индекс добавляется один раз и удаляется не более одного раза — либо как устаревший, либо как вытесненный более сильным кандидатом. Стек занимает O(n) памяти в худшем случае; у дека максимум O(k) живых индексов для окна длины k.

Равные значения, убывание, окно 1 и неверный k

Для next greater: пустой массив, строгий рост/убывание, равные значения не считаются строго большими. В учебном интерфейсе -1 служит признаком отсутствия ответа; если вход допускает отрицательные значения и вызывающей стороне важно отличать настоящий ответ -1, возвращайте индекс либо optional/None. Для окна: k=1, k=n, одинаковые значения; k<=0, k>n и пустой массив с положительным k отклоняются контрактом.

Массивы для проверки строгого сравнения

[2,1,2,4,3] -> [4,2,4,-1,-1], [3,2,1], [1,1], []. Для дека: классический пример с k=3, окно 1, окно на весь массив и неверный размер.

Сигналы «ближайший больший или меньший»

Спрашивается ближайший следующий больший/меньший элемент либо экстремум каждого скользящего окна, и доминируемых кандидатов можно удалить навсегда. Стек отвечает на событие «когда кандидата впервые вытеснили», дек одновременно поддерживает доминирование и срок жизни по индексу.

Когда монотонность теряет нужную информацию?

Для одного глобального максимума достаточно прохода. Для статических запросов на произвольных диапазонах без последовательного движения окна лучше подходят префиксы, sparse table или дерево отрезков в зависимости от операции и обновлений.

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

Вопрос: почему для первого 2 в [2,1,2] ответ не равен второму 2? Ответ: условие строгое, равное значение не снимает индекс.

Мини-проверка: почему вложенный while не даёт O(n²)?

Вопрос: почему вложенный while не создаёт O(n²)? Ответ: суммарно pop выполняется не больше n раз.

Разберите вытеснение индексов значением 4

Проследите стек индексов для [5,3,4,2,6] и отметьте, какие ответы заполняются при каждом pop.

Решите задачу на ближайший меньший элемент

Задача 1

Для каждого элемента массива найдите расстояние до ближайшего строго меньшего элемента справа; если его нет, запишите -1.

Монотонность удаляет кандидатов, которые уже не победят

Монотонный стек хранит нерешённых кандидатов до первого вытеснения. Монотонный дек дополнительно удаляет кандидатов, вышедших из окна, и оставляет максимум или минимум на первом индексе.