Задача: 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, так как для них не найдено большего элемента.

😎 Решение:
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class Solution {
public int[] nextLargerNodes(ListNode head) {
List values = new ArrayList();
while (head != null) {
values.add(head.val);
head = head.next;
}

int[] answer = new int[values.size()];
Stack stack = new Stack();

for (int i = 0; i < values.size(); i++) {
while (!stack.isEmpty() && values.get(stack.peek()) < values.get(i)) {
answer[stack.pop()] = values.get(i);
}
stack.push(i);
}

return answer;
}
}

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