🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1019. Next Greater Node In Linked List
Сложность: 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(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun nextLargerNodes(head: ListNode?): IntArray {
val values = mutableListOf()
var current = head
while (current != null) {
values.add(current.`val`)
current = current.next
}
val answer = IntArray(values.size)
val stack = mutableListOf()
for (i in values.indices) {
while (stack.isNotEmpty() && values[stack.last()] < values[i]) {
answer[stack.removeAt(stack.size - 1)] = values[i]
}
stack.add(i)
}
return answer
}
}
Ставь 👍 и забирай 📚 Базу знаний
