Монотонный стек — это стек, элементы которого располагаются в полностью возрастающем или убывающем порядке. Это ценный инструмент при работе с задачами на основе массивов, требующими определения следующих больших или меньших элементов. Для нашей задачи — поиска следующего большего элемента в массиве — монотонный стек является эффективным подходом, поскольку он позволяет нам отслеживать элементы в структурированном виде, помогая быстро идентифицировать следующий больший элемент. Объединение его со словарем позволяет быстро индексировать элементы, оптимизируя наше решение.

В чем проблема спросить?

Имея два массива, nums1 (подмножество nums2), нам нужно найти следующий больший элемент для каждого числа в nums1 в пределах nums2. Если такого большего элемента нет, мы помечаем его как -1. Проще говоря, мы ищем первое число, которое больше после каждого числа из nums1 в массиве nums2.

Подход:

Наш подход к эффективному решению этой проблемы заключается в использовании монотонного стека и словаря. Мы используем стек, чтобы отслеживать числа, которые являются общими в nums1 и nums2, но еще не нашли следующее большее число в nums2. Словарь помогает нам быстро найти индекс каждого числа в nums1, чтобы быстро заменить ответ для этого числа, как только мы найдем его следующее большее число.

Вот как мы это реализуем:

  • Инициализируйте массив ответов с помощью -1, так как -1 является значением по умолчанию, если мы не находим следующий больший элемент для числа.
  • Используйте понимание словаря, чтобы сопоставить каждое число с его индексом в nums1. Это поможет нам быстро найти позицию числа в nums1, когда нам нужно обновить его ответ.
  • Инициализировать пустой стек. Этот стек поможет нам отслеживать числа в nums2, которые также находятся в nums1 и для которых мы еще не нашли следующий больший элемент. Мы извлекаем число из стека только тогда, когда находим его следующее большее число.
  • Перебрать nums2. Для каждого числа:
  • Если стек не пуст и текущее число больше вершины стека, извлеките вершину стека и обновите ответ для этого числа в массиве ответов.
  • Если текущее число находится в nums1 (что мы можем проверить с помощью словаря), поместите его в стек.

Код решения с построчным объяснением:

    # Initialize the answer array with -1's, as -1 is the default value if we don't find a next greater element
    ans = [-1] * len(nums1)
    # Map each number to its index in nums1 using enumerate, allowing us to quickly locate the position of a number in nums1
    dic = {num: i for i, num in enumerate(nums1)}
    # Initialize an empty stack, which will help us track numbers in nums2 that are also in nums1 and for which we have not yet found the next greater number
    stack = []
    # Iterate over nums2
    for i in range(len(nums2)):
        curr = nums2[i]
        # If the stack is not empty and the current number is greater than the top of the stack, 
        # this means we have found the next greater element for the num from nums1 on top of the stack
        # We pop this number from the stack and update the corresponding position in the answer array with the current number
        while stack and curr > stack[-1]:
            val = stack.pop()
            ans[dic[val]] = curr
        # If the current number exists in dic (indicating it is common between nums1 and nums2),
        # we add it to the stack for potential future comparison
        if curr in dic:
            stack.append(curr)
    return ans

Только код решения:

    ans = [-1] * len(nums1)
    dic = {num: i for i, num in enumerate(nums1)}
    stack = []
    for i in range(len(nums2)):
        curr = nums2[i]
        while stack and curr > stack[-1]:
            val = stack.pop()
            ans[dic[val]] = curr
        if curr in dic:
            stack.append(curr)
    return ans

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

Временная сложность: O(n), где n — количество элементов в nums2. Каждый элемент посещается один раз, и в худшем случае он вставляется и удаляется из стека один раз, что является операцией O (1).

Пространственная сложность: O(n), так как мы используем стек и словарь, который может содержать не более n элементов.

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

Спасибо за обращение и счастливого кодирования! :)