Наибольшая перестановка с использованием стека или очереди

Question

Итак, это вопрос домашней работы, и он просит разработать алгоритм, который найдет наибольшую перестановку, заданную n, массив A, содержащий буквы I и D или длину n, и производит S, массив из n + 1, так что каждое целое число в {0 ... n} появляется ровно один раз.

В массиве A, I представляет собой увеличение, а D - уменьшение.

Таким образом, приведенные примеры являются , если п = 4 и А = IIID Тогда S = 1; 2; 3; 4; 0 , если п = 6, А = IDIDID Тогда S = 5; 6; 3; 4; 1; 2; 0, поскольку он больше S = 5; 6; 2; 4; 1; 3; 0

Алгоритм также должен выполняться в O (n) времени.

В настоящее время я застрял на том, как я хотел бы написать псевдокод для этой проблемы с помощью стека или очереди по мере необходимости в вопросе

Answer 1

Сначала я объясню решение без какого-либо стека или очереди, то мы можем интегрировать их в нашем решении, так как мы имеем n+1 элементов, я рассмотрю последний элемент массива как D.

Таким образом, мы можем разделить элементы массива на 2 части, содержащие все увеличивающиеся элементы, а другие - уменьшающиеся элементы. Итак, если у нас есть k D's в нашем массиве, первые k элементов будут принадлежать первой части, то есть 0, 1, 2, 3.....,(k-1) следующая ((n+1) - k) будет второй частью и представляет I.

Теперь, если у нас есть последовательность D, как DDD, мы возьмем элементы из первой части i.e (k-1), (k-2), (k-3).

Если у нас есть последовательность I, как III, мы возьмем элементы со второй части i.e ((n+1)-2), ((n+1)-1), (n+1).

Позволяет объяснить это на примере:

A : IIIDDIDDDIID //I have added the last D

n = 11

A1 : 0, 1, 2, 3, 4, 5

A2 : 6, 7, 8, 9, 10, 11

Во-первых, мы имеем III, мы размещаем 9, 10, 11 из второй части. Тогда у нас есть DD. Мы размещаем 5, 4 так же, как мы обсуждали в вышеуказанной части, тогда у нас есть I, после чего мы разместим 8 со второй части и так далее.

Продолжая выше, мы имеем: 9, 10, 11, 5, 4, 8, 3, 2, 1, 6, 7, 0

Алгоритм:

Для A1 части массива мы будем держать стек S1 и когда нам нужны элементы, которые мы выскочит из стека.

Для A2 части массива мы будем держать 2 стак S2 и S3, S2 содержит весь A2 массив изначально, и S3 будет пустым изначально. Поэтому, если у меня есть x, тогда я могу вытащить x элементов из стека S2 и добавить его в S3 и, наконец, поместить весь стек S3, чтобы получить ответ.

с использованием приведенного выше примера:

A : IIIDDIDDDID

S1 : 0, 1, 2, 3, 4, 5

S2 : 6, 7, 8, 9, 10, 11

S3 : EMPTY

1) Pop S2 3 раза и поместить Elemen TS в S3 то стек имеет

S2 : 6, 7, 8

S3 : 11, 10, 9

2) Поп S3 и место в ответе.

S3 : EMPTY

ANS : 9, 10, 11

3) Поп-S1 2 раза и место в ответе.

S2 : 0, 1, 2, 3

ANS : 9, 10, 11, 5, 4

И так далее ...