Daily bit(e) C++. Максимум в скользящем окне

Добавлено 16 апреля 2026 в 12:44

Daily bit(e) C++ 28. Распространенная задача на собеседованиях по C++: максимум в скользящем окне.

Рассмотрим распространенную задачу на собеседованиях по C++: максимум в скользящем окне.

Дано: массив целых чисел и размер скользящего окна. Необходимо вычислить максимум для каждой позиции скользящего окна.

Вывод должен быть пустым, если количество входных элементов меньше размера окна.

Ваше решение должно работать за время O(n).

Daily bit(e) C++. Максимум в скользящем окне

В этом примере (входные данные {1,2,-3,5,0}, размер окна 3) вывод будет {2,5,5}.

Прежде чем продолжить чтение решения, попробуйте решить его самостоятельно. Вот ссылка на Compiler Explorer с несколькими тестовыми примерами: https://compiler-explorer.com/z/nYMzEv41j.

Решение

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

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

Таким образом, мы можем запоминать текущих кандидатов, которые исчезают по двум потенциальным причинам:

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

Мы можем достичь этого с помощью простой двухсторонней очереди (std::deque), удаляя первый элемент, когда мы проходим его влияние, и удаляя последние элементы до тех пор, пока последний элемент не станет больше, чем элемент, добавленный в окно.

Это позволяет отсортировать двустороннюю очередь, не выходя за пределы сложности O(n) (поскольку каждый элемент вставляется и удаляется из очереди только один раз).

std::vector<int> max_window(
  const std::vector<int>& nums, size_t window) 
{
    std::deque<size_t> indexes;
    std::vector<int> result;

    // итерация по всем элементам
    for (size_t i = 0; i < nums.size(); i++) 
    {
        // удаляем текущий максимум, если он выходит за пределы окна
        if (!indexes.empty() && i >= window && 
            indexes.front() == i - window)
            indexes.pop_front();
        // удаляем все элементы меньше добавляемого элемента
        // поскольку у них нет шансов быть максимумом
        while (!indexes.empty() && nums[i] > nums[indexes.back()])
            indexes.pop_back();
        // добавляем текущий элемент
        indexes.push_back(i);
        // возвращаем текущий максимум
        if (i >= window - 1)
            result.push_back(nums[indexes.front()]);
    }
    return result;

// Сложность O(n):
// - мы добавляем и удаляем каждый элемент из очереди один раз
// - общее количество сравнений во внутреннем цикле 
//   также в сумме составляет O(n):
//   - при каждом сравнении мы либо удаляем элемент (n раз), 
//     либо добавляем элемент (n раз)
}

Решение

Теги