使用k堆栈对堆栈进行排序，但不能推回原始堆栈

Question

输入k=堆栈数

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

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

所以如果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

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

但是，肯定存在某些具有解决方案的排序，并且它们可能具有不同的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***

但是我们应该推到哪一层呢？就是我被困的地方。如果你能回到in，这个问题将非常容易。

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

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




Answer 1

您可以使用两个辅助堆栈，s1，s2：

• 将原始元素中的每个元素弹出到s1中
• 从原始s1中弹出每个元素，并将其推入s2
  • 对于每个经过的元素，保留较小的元素，在找到另一个较小的元素之前不要推它
  • 最后你得到了较小的一个，所以把它推到r上

  所以看起来应该是：

  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才能解决