11456. Следующий больший элемент

Задан массив целых чисел. Для каждого элемента необходимо найти следующий больший элемент – первый элемент, расположенный правее и строго больше данного.

Если для какого-либо элемента следующий больший элемент отсутствует, выведите -1.

Вход. Первая строка содержит натуральное число n (n ≤ 10⁵).

Вторая строка содержит n натуральных чисел, каждое из которых не превышает 10⁹.

Выход. Для каждого элемента входного массива выведите следующий больший элемент. Если такового нет, выведите -1.

Пример входа	Пример выхода
10 5 3 8 5 7 4 2 1 3 7	8 8 -1 7 -1 7 3 3 7 -1

РЕШЕНИЕ

стек

Анализ алгоритма

Объявим стек целых чисел, который будет использоваться для хранения информации о следующих больших элементах. Будем обрабатывать числа массива 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--)

{

Удаляем c вершины стека все числа, меньшие либо равные 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):

Удаляем c вершины стека все числа, меньшие либо равные 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)