Наступний більший елемент (Розбір)

Оголосимо стек цілих чисел, який буде використовуватись для зберігання інформації про наступні більші елементи. Оброблятимемо числа масиву $a$ послідовно — справа наліво. Під час обробки елемента з індексом $i$:

• видалимо зі стека всі числа, не більші за $a[i]$;

• якщо стек не порожній, то число на вершині стека є наступним більшим елементом для $a[i]$; якщо стек порожній, то як наступний більший елемент запишемо $-1$;

• потім додамо в стек число $a[i]$.

У кожен момент часу стек зберігає числа в порядку спадання. Коли надходить наступне число, зі стека видаляються всі елементи, не більші за нього, після чого це число розміщується на вершині стека.

Приклад

Розглянемо обробку чисел з прикладу.

Реалізація алгоритму

Читаємо вхідні дані.

scanf("%d", &n);
m.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Обробляємо числа послідовно справа наліво.

for (i = n - 1; i >= 0; i--)
{

Видаляємо з вершини стека всі числа, менші або рівні $m[i]$.

  while (!s.empty() && (s.top() <= m[i])) s.pop();

Наступним більшим елементом після $m[i]$ буде число на вершині стека. Якщо стек порожній, то в результатуючий масив $res$ заносимо $-1$.

  if (s.empty()) res.push_back(-1);
  else res.push_back(s.top());

Заносимо число $m[i]$ в стек.

  s.push(m[i]);
}

Перевертаємо і виводимо результатуючий масив.

reverse(res.begin(), res.end());
for (i = 0; i < n; i++)
  printf("%d ", res[i]);
printf("\n");

Реалізація на Python

Читаємо вхідні дані.

n = int(input())
m = list(map(int, input().split()))

Ініціалізуємо списки.

res = []
s = []

Обробляємо числа послідовно справа наліво.

for i in range(n - 1, -1, -1):

Видаляємо з вершини стека всі числа, менші або рівні $m[i]$.

  while s and s[-1] <= m[i]:
    s.pop()

Наступним більшим елементом після $m[i]$ буде число на вершині стека. Якщо стек порожній, то в результуючий список $res$ заносимо $-1$.

  if not s:
    res.append(-1)
  else:
    res.append(s[-1])

Заносимо число $m[i]$ в стек.

  s.append(m[i])

Перевертаємо і виводимо результатуючий список.

res.reverse()
print(*res)