Следующий больший элемент: решение через монотонный стек

Зачем решать задачу «Следующий больший элемент»?

Эта задача — классика собеседований. Она проверяет умение применять монотонный стек для эффективного поиска следующего большего элемента. Освоив её, вы сможете решать похожие задачи: Daily Temperatures, Stock Span и другие. Мы разберём brute force и оптимальный подход на Python.

Условие задачи

Даны два массива: nums1 (подмножество nums2). Для каждого элемента из nums1 найдите первый больший элемент справа в nums2. Если такого нет, верните -1.

Пример

nums1 = [2, 4]
nums2 = [1, 2, 3, 4]
Ответ: [3, -1]

Brute Force: интуиция и код

Простой перебор: для каждого элемента nums1 находим его позицию в nums2, затем идём вправо до первого большего. Минус — повторное сканирование.

Реализация на Python

def nextGreaterElement(nums1, nums2):
    ans = []
    for x in nums1:
        # Находим индекс x в nums2
        idx = nums2.index(x)
        # Ищем первый больший справа
        greater = -1
        for j in range(idx + 1, len(nums2)):
            if nums2[j] > x:
                greater = nums2[j]
                break
        ans.append(greater)
    return ans

Анализ сложности

• Время: O(N × M), где N = len(nums1), M = len(nums2)
• Память: O(1) без учёта выхода

Оптимальное решение: монотонный стек

Заметим, что мы можем вычислить следующий больший элемент для всех элементов nums2 за один проход, используя монотонный убывающий стек. Идём справа налево, поддерживая стек, в котором на вершине — первый больший элемент для текущего.

Алгоритм

1. Создаём стек (пустой) и словарь next_greater.
2. Проходим nums2 справа налево:
3. Пока стек не пуст и вершина стека меньше текущего элемента — удаляем вершину (она никогда не станет следующим большим для будущих элементов).
4. Если стек пуст — следующего большего нет, кладём -1.
5. Иначе — вершина стека и есть следующий больший.
6. Записываем результат в словарь, кладём текущий элемент в стек.
7. Для каждого элемента nums1 берём ответ из словаря.

Реализация на Python

def nextGreaterElement(nums1, nums2):
    stack = []
    next_greater = {}
    
    # Идём справа налево
    for num in reversed(nums2):
        # Удаляем все меньшие элементы из стека
        while stack and stack[-1] < num:
            stack.pop()
        # Если стек пуст — нет большего
        if not stack:
            next_greater[num] = -1
        else:
            next_greater[num] = stack[-1]
        # Кладём текущий элемент в стек
        stack.append(num)
    
    # Собираем ответ для nums1
    return [next_greater[x] for x in nums1]

Пошаговый разбор

Возьмём nums2 = [1, 2, 3, 4].

• Шаг 1: num = 4, стек = [] → next_greater[4] = -1, стек = [4]
• Шаг 2: num = 3, стек = [4], 4 > 3 → next_greater[3] = 4, стек = [3, 4]
• Шаг 3: num = 2, стек = [3, 4], 3 > 2 → next_greater[2] = 3, стек = [2, 3, 4]
• Шаг 4: num = 1, стек = [2, 3, 4], 2 > 1 → next_greater[1] = 2, стек = [1, 2, 3, 4]

Словарь: {4: -1, 3: 4, 2: 3, 1: 2}. Для nums1 = [2, 4] ответ: [3, -1].

Почему монотонный стек работает?

Каждый элемент добавляется в стек один раз и удаляется не более одного раза. Стек всегда хранит элементы в убывающем порядке, поэтому вершина — ближайший больший элемент справа. Это даёт линейное время.

Сложность

• Время: O(N + M), где N = len(nums2), M = len(nums1)
• Память: O(N) для стека и словаря

Практический вывод

Запомните паттерн: «следующий больший элемент» → монотонный стек. Потренируйтесь на задачах Daily Temperatures и Stock Span. Напишите код прямо сейчас, засеките 15 минут — и вы закрепите навык.