使用K堆栈对堆栈进行分类，并且无法将其推回原始堆栈

Question

输入 k =堆栈数

input = 5, 3, 4, 1, 2
output should be  = 5, 4, 3, 2, 1

但是，您只能弹出输入，您不能推到它。output也是您可以返回并推到但不能弹出的另一个堆栈

所以如果k = 1

in = 5, 3, 4, 1, 2  k = (),     out = ()
in = 3, 4, 1, 2     k = 5       out = ()
in = 4, 1, 2        k = 5,3     out = ()
in = 1, 2           k = 5,3,4   out = ()
in = 2              k = 5,3,4   out = 1 // since you know 1 must go first
in = ()             k = 5,3,4   out = 1,2

由于您无法返回到in，因此没有解决方案，您必须报告它。

但是，肯定有某些有解决方案的订单，并且可能具有不同值的k值。例如，如果k = 2有两个堆栈，上述输入排序是否可以解决？

我怎么知道要把哪个堆栈推到？

我的思考过程是

1. pop input
2. pop all k stacks
3. see if any popped values == target, starting with 1 and incrementing
4. if they do == target, push to out
5. if in != target, push to stack k***

但是我们应该推哪个堆栈？是我被卡住的地方。如果您可以回到进去，这个问题将非常容易。

这听起来像是河内型问题的塔，但我不确定。我觉得有一种数学方法可以解决这个问题。有什么想法吗？

编辑：我拥有的另一个直觉是，河内塔有一个限制，您不能将较大的钉子放在较小的钉子上。这对此也很有意义，因为说k = 1，这个问题基本上是河内问题的塔，除了磁盘最初不遵守规则，但如果可能的解决方案，则应遵守规则...

Answer 1

您可以使用两个辅助堆栈S1，S2：

1. 将每个元素从原始元素弹出到S1
2. 弹出原始S1的每个元素并将其推入S2
   • 对于每个经过的元素，保留较小的元素，直到找到另一个较小的元素
   • 最后，您已经有较小的，所以将其推到R
   上
3. 现在重复步骤2，用S2替换S1和Converse，直到没有元素

所以看起来像：

fill(s1,o) // step 1
u = s1, v = s2
repeat
    e = less(v,u) // step 2
    push(r,e)
    swap(u,v)
until empty(u)        

似乎无法删除一个辅助堆栈。我认为问题仅适用于k> = 2。