Сложность: medium
Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.
Пример:
Input: head = [2,1,5]
Output: [5,5,0]
👨💻 Алгоритм:
1⃣Инициализация переменных:
Пройдитесь по всему списку и сохраните значения узлов в массив.
Инициализируйте стек для хранения индексов узлов, которые нужно обработать.
2⃣Поиск следующего большего элемента:
Итерируйте по массиву значений узлов.
Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека.
Добавьте текущий индекс в стек.
3⃣Заполнение оставшихся значений:
Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.
😎 Решение:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
values = []
while head:
values.append(head.val)
head = head.next
answer = [0] * len(values)
stack = []
for i, value in enumerate(values):
while stack and values[stack[-1]] < value:
answer[stack.pop()] = value
stack.append(i)
return answer
Ставь 👍 и забирай 📚 Базу знаний