Монотонный стек: возрастание и убывание
Поддерживайте возрастающий или убывающий стек, чтобы эффективно отвечать на запросы о следующем большем и предыдущем меньшем элементе за O(n)
«Монотонный стек: возрастание и убывание» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое монотонный стек
Монотонный стек — это стек, который поддерживает отсортированный порядок своих элементов: либо элементы всегда возрастают снизу вверх, либо всегда убывают. Перед добавлением нового элемента мы удаляем все элементы, нарушающие инвариант монотонности. Такая ограниченная структура позволяет решать за O(n) задачи, для которых иначе потребовались бы вложенные циклы за O(n²).
the Ключевая идея: каждый элемент добавляется и удаляется не более одного раза, поэтому the общее количество операций при обходе всего массива равно O(n), а не O(n²). В момент удаления элемента мы находим ответ, которого он ожидал.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Следующий больший элемент I
Задача «Следующий больший элемент»: для каждого элемента найти the первый элемент справа, который больше него. Полный перебор с двумя циклами за O(n²) работает слишком медленно. С помощью монотонного стека, упорядоченного по убыванию задача решается за O(n).
Обрабатывайте элементы слева направо. Перед добавлением элемента i удаляйте из стека все элементы, меньшие nums[i]: nums[i] является следующим большим элементом для каждого из них. После обработки всех элементов оставшиеся элементы в стеке не имеют большего элемента справа (ответ = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Следующий больший элемент: пошаговая трассировка алгоритма
Пошагово разберём [2, 1, 2, 4, 3]. Мы поддерживаем убывающий стек индексов, для которых следующий больший элемент ещё не найден.
- i=0, значение=2: стек пуст, помещаем 0. Стек: [0]
- i=1, значение=1: 1 < массив[0]=2, помещаем 1. Стек: [0,1]
- i=2, значение=2: pop 1 (массив[1]=1 < 2), результат[1]=2; теперь массив[0]=2 не < 2, помещаем 2. Стек: [0,2]
- i=3, значение=4: pop 2 (результат[2]=4), pop 0 (результат[0]=4), помещаем 3. Стек: [3]
- i=4, значение=3: 3 < массив[3]=4, помещаем 4. Стек: [3,4]
- Конец: для элементов стека [3,4] результат равен -1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Предыдущий меньший элемент
Монотонные стеки также отвечают на запросы о предыдущем меньшем элементе (PSE): для каждого элемента ищется ближайший меньший элемент слева. Вместо извлечения элементов при встрече большего элемента мы извлекаем элементы при встрече большего или равного элемента и перед помещением нового элемента записываем вершину стека как PSE.
Направление меняется: мы по-прежнему обрабатываем элементы слева направо, но отвечаем на вопросы не во время извлечения, а непосредственно перед помещением нового элемента. Вершина стека в этот момент — ближайший меньший элемент слева. Если стек пуст, меньшего элемента слева нет (ответ равен -1 или специальному маркеру).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Ежедневные температуры: ожидание более тёплых дней
В задаче «Ежедневные температуры» (LeetCode 739) задан массив дневных температур; необходимо вернуть массив, в котором каждый элемент показывает количество дней до более высокой температуры. Это в точности шаблон следующего большего элемента, но вместо большего значения требуется количество дней (разность индексов).
Используйте монотонный убывающий стек индексов. Когда находим более высокую температуру с индексом i, извлекаем из стека все индексы j, для которых temps[j] < temps[i], и устанавливаем result[j] = i - j. Для оставшихся индексов более высокой температуры в будущем нет (результат равен 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Возрастающий и убывающий стек: когда какой использовать
Выбор правильного направления стека имеет решающее значение:
- Монотонный убывающий стек (извлекаем, когда текущий элемент > вершины): отвечает на запросы о следующем большем элементе и предыдущем большем элементе. Используется в задачах о ежедневных температурах, наибольшем прямоугольнике и ловушке для дождевой воды.
- Монотонный возрастающий стек (извлекаем, когда текущий элемент < вершины): отвечает на запросы о следующем меньшем элементе и предыдущем меньшем элементе. Используется при вычислении размаха цен акций и количества видимых людей в очереди.
Помните: элемент, из-за которого происходит извлечение, является ответом на запрос извлечённого элемента — следующим большим или следующим меньшим элементом в зависимости от поддерживаемого инварианта.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Циклический следующий больший элемент
Задача «Следующий больший элемент II» (LeetCode 503): дан циклический массив (после последнего элемента снова идёт первый), необходимо найти следующий больший элемент. Секрет заключается в том, чтобы обработать массив дважды, удвоив диапазон индексов: пройти от 0 до 2n-1 и использовать index % n для перехода к началу. Мы помещаем в стек только индексы от 0 до n-1 (при первом проходе), чтобы не учитывать элементы дважды.
Другой вариант — на втором проходе не помещать новые индексы, а только выполнять извлечение. Это правильно обрабатывает поиск по кругу без фактического дублирования массива и сохраняет объём памяти равным O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Задача о размахе цен акций
В задаче о размахе цен акций заданы ежедневные цены акций; необходимо вычислить размах для каждого дня — количество идущих непосредственно перед ним дней, когда цена была меньше или равна цене сегодня. По сути, это задача о предыдущем большем элементе: размах — расстояние от текущего дня до ближайшего дня со строго большей ценой.
Используйте монотонный убывающий стек. При обработке дня i извлеките все дни с ценой ≤ текущей. Если стек не пуст, размах равен i - stack[-1], а если пуст — i + 1 (текущая цена является максимальной на данный момент). Затем поместите i в стек.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Монотонный стек для видимых людей в очереди
В задаче о количестве видимых людей в очереди люди стоят в очереди, и у каждого есть определённый рост. Человек i может видеть человека j (j > i), если все люди между ними ниже обоих. Для решения используется монотонный убывающий стек.
Обрабатывайте людей справа налево. Поддерживайте убывающий стек ростов. Для каждого человека подсчитайте, сколько людей он может видеть: выполните pop для всех более низких людей (они видны, но после этого оказываются закрыты), а затем добавьте 1, если после извлечения стек не пуст (первый более высокий человек также виден). Общая сложность равна O(n), поскольку каждый человек помещается в стек и извлекается из него не более одного раза.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]Гарантия O(n): почему каждый элемент помещается и извлекается не более одного раза
Гарантия времени O(n) для алгоритмов с монотонным стеком основана на простом амортизационном рассуждении: каждый элемент помещается в стек ровно один раз и извлекается не более одного раза. Ни один элемент не может быть помещён или извлечён более одного раза. Поэтому общее количество операций помещения и pop во всём цикле не превышает 2n, что даёт общую сложность O(n), несмотря на то что вложенный цикл с условием может создавать впечатление сложности O(n²).
На собеседованиях важно уметь сформулировать этот амортизированный анализ. Цикл с условием не выполняется n раз на каждой итерации — он выполняется только столько раз, сколько нужно для извлечения ожидающих элементов, а после извлечения эти элементы исчезают навсегда.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nРаспознавание задач с монотонным стеком
Задаче, скорее всего, нужен монотонный стек, если требуется найти ближайший больший или меньший элемент, размах цен, видимые элементы в ряду или площади на основе гистограммы. Ищите такие ключевые слова и закономерности: для каждого элемента требуется ответ от ближайшего подходящего элемента в одном из направлений — слева или справа.
Если решение перебором просматривает элементы слева или справа от каждого элемента (O(n²)), замените такой просмотр монотонным стеком. Стек «запоминает» возможные ответы, отбрасывает неподходящие и извлекает правильный ответ именно в тот момент, когда он нужен.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Быстрая проверка
Проверьте своё понимание концепций структур данных & алгоритмов — подготовки к собеседованию по программированию, рассмотренных в этом уроке.
Итоги урока
В этом уроке вы узнали: монотонный стек поддерживает возрастающий или убывающий порядок, извлекая элементы, нарушающие инвариант, перед помещением нового элемента, убывающий стек отвечает на вопросы о следующем и предыдущем большем элементе, а возрастающий — о следующем и предыдущем меньшем элементе, а также каждый элемент помещается и извлекается не более одного раза, что даёт общее время O(n), а не O(n²). Далее мы применим монотонный стек для поиска наибольшего прямоугольника в гистограмме.
Часто задаваемые вопросы
Урок «Монотонный стек: возрастание и убывание» бесплатный?
Да — полный текст урока «Монотонный стек: возрастание и убывание» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Монотонный стек: возрастание и убывание»?
Поддерживайте возрастающий или убывающий стек, чтобы эффективно отвечать на запросы о следующем большем и предыдущем меньшем элементе за O(n) Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Монотонный стек: возрастание и убывание»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Монотонный стек: возрастание и убывание
- Наибольший прямоугольник в гистограмме
- Максимум в скользящем окне с монотонной декой
- Заполнение водой: стек и два указателя