Монотонный стек: следующий больший элемент
Отвечайте на запросы о диапазонах за один проход
«Монотонный стек: следующий больший элемент» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Задача о следующем большем элементе
Для каждого числа нужно найти первое большее значение справа от него. Полный перебор работает за O(n в квадрате), но монотонный стек решает задачу за один проход.
Что означает «монотонный»
Монотонный стек хранит значения в отсортированном порядке — в данном случае по убыванию. Поэтому, как только этот порядок нарушается, мы понимаем, что ответ найден.
Храните индексы, а не значения
Помещайте в стек индексы, а не сами числа. Так Вы точно знаете, какую позицию заполнить, когда появится больший элемент.
stack = []
ans = [-1] * len(nums)Идите слева направо
Один раз пройдите по массиву. На каждом индексе Вы либо извлекаете уже обработанные элементы, либо помещаете текущий индекс для дальнейшей обработки.
for i in range(len(nums)):Извлекайте меньшие элементы
Пока текущее значение больше значения по индексу на вершине, этот элемент на вершине наконец нашёл свой следующий больший элемент.
while stack and nums[i] > nums[stack[-1]]:Запишите ответ
Извлеките индекс с вершины и установите для него текущий ответ. Каждый индекс обрабатывается ровно один раз, поэтому общая работа остаётся линейной.
j = stack.pop()
ans[j] = nums[i]Поместите элемент и продолжайте
После обработки всех меньших элементов поместите текущий индекс в стек, чтобы он дождался своего будущего большего элемента.
stack.append(i)Для оставшихся нет ответа
Индексы, оставшиеся в стеке в конце, так и не встретили большего значения. Для них сохраняется значение по умолчанию -1, означающее, что такого элемента нет.
Почему получается O(n)
Каждый индекс помещается и извлекается ровно один раз. Даже с внутренним циклом while общая работа за весь просмотр остаётся линейной.
Измените правило для следующего меньшего
Нужен следующий меньший элемент? Вместо этого поддерживайте стек в возрастающем порядке, изменив сравнение с «больше» на «меньше».
while stack and nums[i] < nums[stack[-1]]:Шаблон, а не трюк
Эта идея применяется в запросах о диапазонах, ценах акций и площадях гистограмм. Монотонный стек — важный шаблон для соревнований, который стоит запомнить.
Быстрая проверка
Вы решаете задачу о следующем большем элементе с помощью монотонного стека. Почему общее время работы линейно?
Итоги: один проход — много ответов
Вы использовали убывающий монотонный стек индексов, чтобы найти следующие большие элементы за O(n). Этот шаблон открывает путь ко многим задачам о диапазонах. 🚀
Часто задаваемые вопросы
Урок «Монотонный стек: следующий больший элемент» бесплатный?
Да — полный текст урока «Монотонный стек: следующий больший элемент» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Монотонный стек: следующий больший элемент»?
Отвечайте на запросы о диапазонах за один проход Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Монотонный стек: следующий больший элемент»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Стеки для сопоставления скобок
- Монотонный стек: следующий больший элемент
- Очереди и collections.deque
- Максимум в скользящем окне с деком