使用堆栈或队列的最大排列

Question

所以这是一个家庭作业问题，它要求设计一个算法，给出n，一个数组A，包含字母I和D或长度为n的最大排列，并产生S，一个数组n + 1，使得{0 ... n}中的每个整数只出现一次。

在数组A中，I表示递增，D表示递减。如果n = 4且A = IIID，则给出的示例为 ，则如果n = 6且A = IDIDID，则S = 5; 6; 3; 4; 1; 2; 0因为它大于S = 5; 6; 2; 4; 1; 3; 0

算法还需要在O（n）时间内运行。

我目前停留在如问题

Answer 1

首先，我会解释没有任何堆栈或队列解决方案需要我将如何编写使用堆栈或队列这个问题的伪代码，那么我们就可以整合他们在我们的解决方案，因为我们有n+1元素，我会考虑阵列的最后一个元素是D。

因此，我们可以将数组的元素分成两部分，一部分包含所有增加的元素，另一部分包含递减的元素。因此，如果我们的阵列中有kD，则前k个元素将属于第一个元素，即0, 1, 2, 3.....,(k-1)下一个((n+1) - k)将是第二个部分并代表I。我们将从第一部分即（k-1），（k-2），（k-3）中取出一些元素，如DDD。

如果我们有一个像III这样的I的序列，我们将采用第二部分的元素，即((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我就可以从S2堆栈中弹出x元素，并将它添加到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在S3 TS那么栈具有

S2 : 6, 7, 8

S3 : 11, 10, 9

2）POP S3和答案的地方。

S3 : EMPTY

ANS : 9, 10, 11

3）在答题流行S1的2倍和地点。

S2 : 0, 1, 2, 3

ANS : 9, 10, 11, 5, 4

等等......