Next Greater Element
Published in
2 min readMar 28, 2021
Разбор
Испльзуя 1й и 2й массив можно создать хэш-таблицу, ктр будет содержать пары { элемент -> след.больший элемент }. Тогда задача будет выполнена. Но как создать такую таблицу за линейное время ?!
В этом нам может помочь стек. Итак идея в следующем.
- Проходим по 2му массиву и каждый текущий элемент кидаем в стек, но одновременно с этим будем заполнять хэш-таблицу следующим образом.
- Если текущий элемент 2го массива больше, чем посл.элемент стека, то обновляем хэш-таблицу: ключом теперь будет посл.элемент стека, а значением текущий элемент.
- После прохождения цикла по 2му массиву в стеке могут остаться элемент, для которых нет след.большего элемента, присваиваем им -1.
- После этого у нас будет готовая хэш-таблица, проходим по 1му массиву и формируем результирующий массив.
Основаная идея заключается в том, что элемент выскакивает из стека всякий раз, когда для него обнаруживается следующий больший элемент. Таким образом, в стеке остаются те элементы, для которых в массиве не существует следующего большего элемента.
Давайте посмотрим детали реализации ниже.
Реализация
