Сгенерируйте все числа до N в лексикографическом порядке, используя стек

Учитывая целое число N , задача состоит в том, чтобы напечатать все числа до N в лексикографическом порядке .

Примеры:

Input: N = 20
Output: 1 10 11 12 13 14 15 16 17 18 19 2 3 4 5 6 7 8 9

Input: N = 5
Output: 1 2 3 4

Input: N = 19 
Output: 1 10 11 12 13 14 15 16 17 18 2 3 4 5 6 7 8 9 

Подход:

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

• Инициализируйте два стека stackA и stackB . Вставьте 1 в тип данных String в stackA .
• Затем выполните итерацию от номера 2 до N ( i = 2 до N-1 ) :
  • Для каждого числа преобразуйте текущее число в его строковый эквивалент и сверьтесь с элементом наверху стекаA .
  • Если элемент наверху stackA лексикографически меньше текущего числа:
    • Затем извлеките элемент из стека A и поместите эти извлеченные элементы в стек B до тех пор, пока элемент просмотра стека A не станет меньше текущего числа или пока стек A не станет пустым.
    • Поместите текущий номер в форме String в stackA .
    • Затем извлеките все элементы из stackB и поместите их в stackA.
• Теперь все числа до N были помещены в stackA в строковом типе данных. Извлекайте все элементы из stackA , пока stackA не станет пустым.
• Теперь все числа печатаются в лексикографическом порядке.

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

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

Статьи по Теме:

• Сгенерировать все числа до N в лексикографическом порядке
• Введение в стек — учебные пособия по структурам данных и алгоритмам