Два приёма, которые регулярно встречаются на собеседованиях, в алгоритмических задачах и в реальной разработке: prefix sum и монотонный стек. Они помогают резко сократить сложность решения — с O(n²) до O(n) или O(n log n).
Prefix Sum — когда нужно быстро считать суммы на отрезках
Идея простая: строим массив префиксных сумм, гдеpref[i] = a[0] + a[1] + ... + a[i-1]
Тогда сумма на отрезке [l, r] считается за O(1):
sum(l, r) = pref[r + 1] - pref[l]
Где это полезно:
- сумма элементов на подмассиве
- поиск количества подотрезков с заданной суммой
- задачи на баланс, частоты, накопления
- 2D-задачи: суммы в матрице через префиксные суммы 🧮
Важно:
- для многих задач удобнее хранить
pref[0] = 0 - если есть отрицательные числа, двух указателей часто недостаточно, а prefix sum + hashmap работает отлично
- в задачах “найти количество подмассивов с суммой k” обычно используют словарь частот префиксов
Пример идеи:
если curr_prefix - k уже встречался раньше, значит существует подмассив с суммой k.
Монотонный стек — когда нужен ближайший больше/меньше элемент
Это стек, в котором элементы хранятся в возрастающем или убывающем порядке. Он нужен для задач вида:
- ближайший меньший слева/справа
- ближайший больший слева/справа
- stock span
- largest rectangle in histogram
- daily temperatures 🌡️
Как работает:
проходим массив один раз и поддерживаем стек индексов. Перед добавлением нового элемента удаляем из стека всё, что нарушает монотонность.
Почему это быстро:
каждый элемент добавляется в стек и удаляется из него не более одного раза. Итоговая сложность — O(n) 🚀
Пример логики:
- нужен следующий больший элемент справа
- идём слева направо
- пока текущий элемент больше вершины стека — нашли ответ для элементов в стеке
- затем кладём текущий индекс в стек
Когда что использовать
Prefix Sum:
- если вопрос про суммы, накопления, количество подотрезков
- если нужны быстрые запросы на диапазоне
Монотонный стек:
- если вопрос про “ближайший слева/справа”
- если нужно оптимально обрабатывать сравнение соседних по смыслу элементов
Частая ошибка
Разработчики иногда пытаются решать задачу перебором или вложенными циклами, хотя по формулировке уже видно паттерн:
- “сумма на отрезке” → думай про prefix sum
- “первый меньший/больший справа или слева” → думай про монотонный стек
Умение быстро узнавать такие шаблоны — важный навык для backend, data, ML и algorithmic coding 💡
Сохраняйте пост, если хотите быстрее распознавать алгоритмические паттерны в задачах. И загляните в подборку каналов про IT — там ещё больше практики, разборов и полезных материалов 📚