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

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

Следующий больший элемент для элемента x – это первый строго больший элемент справа от x в массиве. Для элементов, у которых не существует следующего большего элемента, выведите -1.

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

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

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

РЕШЕНИЕ

стек

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

Объявим стек целых чисел, который будет хранить информацию о следующих больших элементах. Будем обрабатывать числа последовательно справа налево. При обработке i-го числа:

· удалим из стека числа, не большие i-го;

· число на вершине стека будет следующим элементом, большим i – го числа. Если стек пуст, то следующий больший элемент положим равным -1;

· занесем в стек 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");