娱乐 每 日 算 法 挑 战 【第5期】

[卡泽]

用3个栈的普适方法：将3个栈命名为栈1，栈2，栈max

全压进一个栈1，pop栈1放入栈max。

循环{

pop栈1和max，比较。若栈max pop的更大，则把栈1pop的丢进栈2。反之，将栈max pop的丢进栈2，栈1pop的丢进栈max。（这一步比较了栈1顶和栈max顶的大小，并把小的那个丢进了栈2）

当栈1空时，把栈2全部倒回栈1。

}

最后栈max里就是想要的排序了。这个算法的本质是用3个栈实现了比大小。然后每次把找到的最大元放进一个栈里。时间复杂度O(n^2)。很trivial的算法，但提供了上限（最多用3个栈）。两个栈和O(logn)的算法我再想想

 

[卡泽]

感觉题目的例子有点奇怪？输入是：

5
4 5 1 2 3

那么怎么先压入3再压入2呢？还是这里写错了？

[卡泽]

我有点没有理解题目的意思。。

按我目前的理解：

如果输入已经排好序了，0个栈直接输出即可。

如果输入形如:(3,2,1)(5,4)(8,7,6)(9,10,11)(14,13,12)，即输入可以被分为许多组。每个组内要么正序要么逆序。即：如果某个组之前的所有组包含1-n，且这个组的长度是k，则这个组形如:(n+1,n+2,...n+k)或(n+k,n+k-1,...n+1)。此时用1个栈。

任何其他情况用两个栈：全部倒进一个栈，然后依次从栈1倒进栈2，再从栈2倒进栈1。每次遇到想要的数，就pop一下。