Leetcode 496. Следващ по-голям елемент I — Python.

Монотонният стек е стек, който поддържа своите елементи в напълно нарастващ или намаляващ ред. Това е ценен инструмент, когато се занимавате с проблеми, базирани на масиви, които изискват идентифициране на следващите по-големи или по-малки елементи. За нашия проблем — намиране на следващия по-голям елемент в масив — монотонният стек е ефективен подход, тъй като ни позволява да следим елементите по структуриран начин, помагайки бързо да идентифицираме следващия по-голям елемент. Сдвояването му с речник позволява бързо индексиране на елементи, оптимизирайки нашето решение.

Какъв е проблемът да питаш?

Дадени са два масива, 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 елемента.

Ако сте намерили тази статия за полезна, помислете да ме последвате за повече упътвания като тази. Не се колебайте да се свържете с нас, ако се борите с предизвикателство при програмирането, имате обратна връзка за статията или ако има конкретен проблем, с който искате да се справя следващия път.

Благодаря, че се свързахте и приятно кодиране! :)