Лексикографически наибольшая перестановка путем последовательной вставки элементов массива на концах

Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы найти лексикографически наибольшую перестановку, последовательно вставляя элементы массива в начало или конец другого массива.

Примеры:

Input: arr[] = {3, 1, 2, 4}
Output: 4 3 1 2
Explanation:
The permutations that can be created by sequentially inserting the array elements to the front or the back of the container are {3, 1, 2, 4}, {1, 3, 2, 4}, {2, 3, 1, 4}, {2, 1, 3, 4}, {4, 1, 3, 2}, {4, 2, 3, 1}, {4, 2, 1, 3}, and {4, 3, 1, 2}. Out of which {4, 3, 1, 2} is the lexicographically largest permutation.

Input: arr[] = {1, 2, 3, 4, 5}
Output: 5 4 3 2 1

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

• Инициализируйте очередь, скажем, DQ , в которой хранится текущее состояние контейнера.
• Инициализируйте переменную, скажем, mx , которая хранит максимум до каждого индекса, представляющего 1 ^-й элемент двухсторонней очереди DQ .
• Пройдите по заданному массиву arr[] и, если текущий элемент arr[i] >= mx , затем вставьте arr[i] в начало двухсторонней очереди DQ и обновите значение mx . В противном случае вставьте arr[i] в конец двухсторонней очереди DQ .
• После выполнения вышеуказанных шагов выведите элементы, хранящиеся в двухсторонней очереди DQ , как результирующую наибольшую перестановку.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)