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

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

Примеры :

Input: N = 5, A[] = {2, 4, 4, 1, 3}
Output: {2, 1, 3}
Explanation: All possible subsequences of the array 
after removing exactly one integer are : 
On deleting 2: {4, 4, 1, 3}
On deleting 4: {2, 1, 3}
On deleting 1: {2, 4, 4, 3}
On deleting 3: {2, 4, 4, 1}
Lexicographically smallest among these is {2, 1, 3}

Input: N = 6, A[] = {1, 1, 1, 1, 1, 1}
Output: {}

Подход: Чтобы решить проблему, следуйте следующему наблюдению:

Наблюдение:

It can be observed easily that to make a subsequence of an array lexicographically smallest, first element which is greater than its next element must be removed. 

Основываясь на приведенном выше наблюдении, для достижения решения можно выполнить шаги, упомянутые ниже:

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

Ниже приведена реализация описанного выше подхода.

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