Задача: 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<Int>()
        var current = head
        while (current != null) {
            values.add(current.`val`)
            current = current.next
        }
        
        val answer = IntArray(values.size)
        val stack = mutableListOf<Int>()
        
        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
    }
}

Ставь 👍 и забирай 📚 Базу знаний