Приём с монотонным стеком
Применяйте монотонный стек для решения задач daily-temperatures, largest-rectangle-in-histogram и next-greater-element за O(n)
«Приём с монотонным стеком» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое монотонный стек
Монотонный стек — это стек, элементы которого поддерживают упорядоченное инвариантное условие. В возрастающем монотонном стеке элементы увеличиваются снизу вверх, а в убывающем монотонном стеке — уменьшаются снизу вверх. Когда новый элемент нарушает это условие, элементы извлекаются из стека до его восстановления, после чего новый элемент помещается в стек.
Этот простой механизм позволяет за O(n) отвечать на запросы о «ближайшем большем элементе» и «ближайшем меньшем элементе», для которых наивное решение потребовало бы O(n²) вложенных циклов.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Следующий больший элемент (LeetCode 496)
Для каждого элемента найдите первый строго больший элемент справа от него. Решение методом полного перебора за O(n²) просматривает элементы справа от каждой позиции. При использовании монотонного стека поддерживайте убывающий стек индексов. Когда встречается больший элемент, извлеките все индексы меньших элементов: их «следующим большим элементом» будет текущий элемент. Для оставшихся индексов следующего большего элемента нет, поэтому ответ для них равен -1.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Следующий больший элемент в циклическом массиве
LeetCode 503 «Следующий больший элемент II»: та же задача, но массив рассматривается как циклический. Достигнув конца, вернитесь к началу и продолжите проверку. Приём состоит в том, чтобы пройти массив дважды (с индексами от 0 до 2n-1) и использовать i % n для обращения к исходному массиву. Добавляйте в стек только индексы из диапазона [0, n-1], чтобы избежать повторной обработки.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Ежедневные температуры: полное решение
Повторим задачу LeetCode 739: сколько дней для каждого дня нужно ждать до более высокой температуры? Монотонный стек хранит индексы дней с температурами в убывающем порядке. Когда найден более тёплый день i, извлеките из стека все индексы j более холодных дней и сохраните result[j] = i - j. Дни, оставшиеся в стеке, так и не встретили более тёплый день, поэтому их результат остаётся равным 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Предыдущий меньший элемент
Запрос о «предыдущем меньшем элементе» означает: для каждого элемента найдите ближайшее меньшее значение слева от него. Используйте возрастающий монотонный стек и обрабатывайте элементы слева направо. Перед добавлением индекса i вершина стека содержит предыдущий меньший элемент, потому что все элементы, большие чем nums[i], были извлечены во время предыдущих добавлений, когда появившиеся большие элементы вытеснили их.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Наибольший прямоугольник в гистограмме
LeetCode 84 «Наибольший прямоугольник в гистограмме»: используйте монотонный возрастающий стек индексов. Для каждого столбца извлекайте все столбцы, которые выше текущего. Для каждого извлечённого столбца высотой h его правая граница — текущий индекс i, а левая граница — вершина нового стека + 1 (или 0, если стек пуст). Площадь = h × (правая граница - левая граница). Добавьте фиктивный столбец высотой 0, чтобы в конце извлечь все оставшиеся столбцы.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Наибольший прямоугольник (LeetCode 85)
LeetCode 85 «Наибольший прямоугольник» расширяет задачу о гистограмме на двоичную матрицу размером 2D. Для каждой строки вычислите накопленные высоты столбцов: если matrix[row][col] == '1', высота равна количеству последовательных единиц выше этой ячейки и включая её. Затем примените алгоритм поиска наибольшего прямоугольника в гистограмме к массиву высот каждой строки. Время работы: O(m × n) для матрицы размером m×n.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Задержка дождевой воды: подход со стеком
LeetCode 42 «Задержка дождевой воды» со стеком: поддерживайте убывающий стек индексов. Когда встречается более высокий столбец, образуется впадина. Извлеките дно впадины; вычислите ширину воды как (текущий индекс - вершина стека - 1), а высоту — как (минимум из текущего столбца и столбца на новой вершине стека - высота впадины). Суммируйте все полученные объёмы. Время работы: O(n), занимаемая память: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Как распознавать задачи для монотонного стека
Признаки того, что монотонный стек — подходящий инструмент: в задаче требуется найти следующий или предыдущий больший/меньший элемент, ответ для каждого элемента зависит от элементов в определённом направлении или наивное решение за O(n²) предполагает просмотр элементов слева или справа для каждого элемента. Стек хранит кандидатов, которые могут стать ответами для будущих элементов, и отбрасывает их, как только появляется лучший кандидат.
Всегда заранее решайте, какой стек использовать: возрастающий (для следующего или предыдущего меньшего элемента) или убывающий (для следующего или предыдущего большего элемента), а также в каком направлении обрабатывать элементы.
Амортизированный анализ O(n)
Сначала алгоритмы на монотонных стеках могут выглядеть как O(n log n) или O(n)² из-за цикла с условием внутри цикла перебора. Но каждый элемент добавляется в стек не более одного раза и извлекается из него не более одного раза. Общее количество операций добавления равно n, а общее количество операций извлечения также не превышает n. Поэтому за все итерации выполняется 2n операций — амортизированно O(n), а не O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nИтоги: выбор инвариантного условия монотонного стека
Выбирайте направление стека в зависимости от запроса. Для следующего большего элемента используйте убывающий стек — извлекайте элементы, когда текущий элемент больше. Для следующего меньшего элемента используйте возрастающий стек — извлекайте элементы, когда текущий элемент меньше. Для наибольшего прямоугольника используйте возрастающий стек и извлекайте элементы, когда появляется более низкий столбец. Для максимума в скользящем окне используйте убывающую двустороннюю очередь и удаляйте элементы с обоих концов.
Если перед написанием кода записать инвариантное условие в комментарии, логика станет понятнее, а отладка ускорится.
Быстрая проверка
Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали, что монотонный стек поддерживает упорядоченное инвариантное условие, извлекая нарушающие его элементы перед добавлением нового элемента, убывающие стеки отвечают на запросы о следующем большем элементе, а возрастающие — о следующем меньшем элементе, а общее время работы амортизированно равно O(n), поскольку каждый элемент добавляется в стек и извлекается из него не более одного раза. Далее мы реализуем очереди с помощью стеков и стеки с помощью очередей.
Часто задаваемые вопросы
Урок «Приём с монотонным стеком» бесплатный?
Да — полный текст урока «Приём с монотонным стеком» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Приём с монотонным стеком»?
Применяйте монотонный стек для решения задач daily-temperatures, largest-rectangle-in-histogram и next-greater-element за O(n) Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Приём с монотонным стеком»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Реализация стека и его применение
- Реализация очереди и дека
- Приём с монотонным стеком
- Взаимная имитация стека и очереди