ЕГЭОГЭ
Задания № 17, 24 · ЕГЭ

Префиксный минимум

Минимум на каждом начальном участке массива
3 мин чтенияСложность: Обновлено 29 сентября 2026

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

Префиксный минимумПрефикс — начальная часть последовательности; минимум — наименьшее значение.
Префиксный минимум массива \(a\) в позиции \(i\) — это минимальный элемент среди \(a_0, a_1, \ldots, a_i\). Обозначают его, например, как \(p_i\) или \(min_i\). Позиции могут начинаться с нуля или с единицы — это зависит от принятой в задаче нумерации.

Формула

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

\[p_i=\min(a_0,a_1,\ldots,a_i),\qquad p_i=\min(p_{i-1},a_i)\quad (i\ge 1)\]

Вычисление занимает \(O(n)\) времени. Если хранить только текущий минимум, дополнительная память равна \(O(1)\); если сохранить весь массив префиксных минимумов, потребуется \(O(n)\) памяти. Такой массив часто используют в задачах, где нужно быстро отвечать на запросы о минимуме на отрезке, начинающемся с первого элемента.

№
Пример

Пусть \(a=[7,3,5,2,6]\). Последовательно получаем: \(p_0=7\), \(p_1=\min(7,3)=3\), \(p_2=\min(3,5)=3\), \(p_3=\min(3,2)=2\), \(p_4=\min(2,6)=2\). Массив префиксных минимумов: \([7,3,3,2,2]\).

!
Не путайте с префиксным максимумом

Префиксный минимум выбирает наименьшее значение, а префиксный максимум — наибольшее. Для максимума в формуле используется \(\max\), а при обновлении — сравнение с большим значением. Также префиксный минимум не равен минимуму всего массива: он меняется по мере расширения префикса.

Проверьте себя

Каков массив префиксных минимумов для массива \([4,6,1,3]\)?

Главное за минуту

Главное

  • Префиксный минимум в позиции \(i\) — минимум элементов от начала массива до \(i\).
  • Его вычисляют одним проходом: \(p_i=\min(p_{i-1},a_i)\).
  • Префиксные минимумы могут оставаться неизменными или уменьшаться, но никогда не увеличиваются.