栈、队列、堆

数据结构

n个整数的无序数组，找到每个元素后面比它大的第一个数，要求时间复杂度为O(N)，用栈+栈底指针

或者是以下思路

int main() {
  stack<int> s;
  vector<int> input = {2,5,7,1,6,9};
  vector<pair<int, int> > out;
  for (int i = 0; i < input.size(); i++) {
    while (!s.empty() && input[i] > s.top()) {
      out.push_back(make_pair(s.top(), input[i]));
      s.pop();
    }
    s.push(input[i]);
  }
  for (auto k : out) {
    printf("%d %d\n", k.first, k.second);
  }
}

栈---中序转后序表达式
入列操作会将整数0-9按照被插入栈，出列操作会打印出返回值，判断哪种序列是不可能产生的----依据:序列中比某数小的后边必然将倒序

用一个双向队列实现两个栈
保证每个栈操作只需要常数次的双向队列操作

两个栈实现的队列
入栈时入栈1，出栈时将栈1的所有元素压入栈2，然后从栈2出。均摊操作为o(1)，但最坏情况为O(N)
还有一种比较简单的情况是

两个队列实现一个栈。思路也比较简单 一个队列作入栈、另外一个队列中转，两个队列的角色每轮互换。
一个队列与两个队列实现的复杂度是一样的，根本不需要两个队列进行操作。队列无法改变元素顺序，无法使用类似栈的lazy evaluation的方式降低复杂度。

一个队列实现的栈
使用一个队列实现一个栈，使得每个栈操作所需的队列操作数量为线性级别。每次入队的时候将队列倒转，这样入队的元素就是第一个了。

有限个栈实现的队列
要求最坏情况也为O(1)
https://www.zhihu.com/question/53233538/answer/197402105
hard
http://www.cnblogs.com/ikesnowy/p/7157813.html

用三个栈实现的双向队列
要求均摊操作为O(1) 计算均摊操作要总的操作数目带来的代价(比如入栈、出栈次数)/总操作数

我们首先设想一种情况就是如果我们用两个栈来实现双向队列，则是一个left栈，一个right栈。pushFront进左栈，pushback进右栈，然后当一侧的栈空时需要将另外一侧的栈的倒过来，所以我们可以很明显的看出最坏的情况是来回倒的情况，发生的操作数为2*(n + n-1 + ... + 1) = ~n^2 因此均摊操作为O(n)

然后我们使用三个栈:
三个栈分别命名为左中右。
左侧栈和右侧栈负责模拟队列，和用两个栈模拟队列的方法类似。
由于是双向队列，左栈和右栈会频繁的倒来倒去，因此每次都只倒一半的元素可以有效减少开销。
有一侧栈为空时，另一侧栈中上半部分先移动到中间栈中，下半部分倒到另一侧栈里，再从中间栈拿回上半部分元素。
这样可以确保接下来的 pop 操作一定是常数级别的。
证明过程如下:
3*(n + n/2 + n/4 + n/8 + ... + 1) = ~n 则均摊为O(1) 算数别求错了 里边系数3为n/2 * 2 + n/2* 4包括一半元素进入中间栈 另一半元素去另外一侧，中间栈一半元素回到原栈这3个操作过程。

namespace _1._4._31
{
    class Deque<Item>
    {
        Stack<Item> left;
        Stack<Item> middle;
        Stack<Item> right;

        // 构造一条新的双向队列。
        public Deque()
        {
            this.left = new Stack<Item>();
            this.middle = new Stack<Item>();
            this.right = new Stack<Item>();
        }

        // 向双向队列左侧插入一个元素。
        public void PushLeft(Item item)
        {
            this.left.Push(item);
        }

        // 向双向队列右侧插入一个元素。
        public void PushRight(Item item)
        {
            this.right.Push(item);
        }

        // 当一侧栈为空时，将另一侧的下半部分元素移动过来。
        private void Move(Stack<Item> source, Stack<Item> destination) 
        {
            int n = source.Size();
            // 将上半部分元素移动到临时栈 middle
            for (int i = 0; i < n / 2; ++i)
            {
                this.middle.Push(source.Pop());
            }
            // 将下半部分移动到另一侧栈中
            while (!source.IsEmpty())
            {
                destination.Push(source.Pop());
            }
            // 从 middle 取回上半部分元素
            while (!this.middle.IsEmpty())
            {
                source.Push(this.middle.Pop());
            }
        }

        // 检查双端队列是否为空。
        public bool IsEmpty()
        {
            return this.right.IsEmpty() && this.middle.IsEmpty() && this.left.IsEmpty();
        }

        // 从右侧弹出一个元素。
        public Item PopRight()
        {
            if (this.right.IsEmpty())
            {
                Move(this.left, this.right);
            }

            return this.right.Pop();
        }

        // 从左侧弹出一个元素。
        public Item PopLeft()
        {
            if (this.left.IsEmpty())
            {
                Move(this.right, this.left);
            }

            return this.left.Pop();
        }

        // 返回双端队列的大小。
        public int Size()
        {
            return this.left.Size() + this.middle.Size() + this.right.Size();
        }
    }
}

出栈顺序问题

N个数依次入栈，出栈顺序有多少种？
令h(0)=1,h(1)=1，卡特兰数满足递推式：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 ，h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5；
另类递推式：h(n)=h(n-1)*(4*n-2)/(n+1)；

递推关系的解为：h(n)=C(2n,n)/(n+1) (n=1,2,3,...)；

递推关系的另类解为：h(n)=C(2n,n)-C(2n,n+1)(n=1,2,3,...)；

常规分析

首先，我们设f（n）=序列个数为n的出栈序列种数。同时，我们假定第一个出栈的序数是k。 第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。 此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。 看到此处，再看看卡特兰数的递推式，答案不言而喻，即为f（n）=h（n）= C（2n,n）/（n+1）= C（2n,n）-C（2n,n+1）（n=1，2，3，……）。 最后，令f（0）=1，f（1）=1。

非常规分析

对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。(这种一一对应的关系离不开题目中的依次二字，好好考虑下)

在2n位二进制数中填入n个1的方案数为C(2n,n),不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。

不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。

因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。

显然，不符合要求的方案数为C(2n,n+1)。由此得出输出序列的总数目=C(2n,n)-C(2n,n+1)=C(2n,n)/(n+1)=h(n+1)。

类似问题 买票找零
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)

最终结果：C(2n,n)-C(2n,n+1)

题目
　　定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 0(1)

分析
　　要在O(1)的时间获取最小元素，需要将这个最小元素保存下来。但只用一个变量去保存最小的元素可以吗？如果在使用栈的过程中将这个最小元素pop出去了，因为栈中的元素是无序的，则无法在O(1)的时间找到第二小的值做为最小元素。

　因此我们要么要将栈中的元素在push的过程中排序，要么需记录栈的每一个位置所对应的的最小值，具体做法是借助一个辅助栈，在辅助栈的同一位置上push进一个原栈从栈底至该位置的最小值。辅助栈的栈顶元素永远是最小的，每次push新元素后，

　如果新元素比辅助栈顶元素小，将该元素也push进辅助栈，反之，仍push原最小元素。过程中保持辅助栈和原栈大小一致。
　
　
题目:栈排序 不允许使用其他辅助的数据结构

在上面这个例子中，出栈序列是 3,2,1，因此实现了对数组的排序。
遗憾的是，有些时候，仅仅借助一个栈，不能实现对数组的完全排序。例如
给定数组 2,1,3，借助一个栈，能获得的字典序最大的出栈序列是 3,1,2：
2 入栈；1 入栈；3 入栈；3 出栈；1 出栈；2 出栈。

请你借助一个栈，对一个给定的数组按照出栈顺序进行从大到小排序。当无
法完全排序时，请输出字典序最大的出栈序列。

采用类似贪心的策略
while(1)
{
if(sum[tail]>zhan[head]||!head) { //如果数组当前元素后缀值没有比stack.top大，则stack.pop
for(int i=tail;i<=n;i++) //否则一直添加直到后缀的最大值
if(a[i]!=sum[tail]) zhan[++head]=a[i];
else
{
tail=i+1;
printf("%d ",a[i]);
break;
}
} else {
printf("%d ",zhan[head--]);
}
if(tail>n) break;
}

变形:使用两个栈实现排序
这道题让我们对栈进行升序排序，栈顶放最大的元素，而且限定了我们只能用一个辅助栈。那么我们的思路是，先取出给定栈的栈顶元素存入到一个临时变量中，然后我们看辅助栈的栈顶元素是否大于取出的元素，大的话就把辅助栈的栈顶元素压入给定栈中，直到辅助栈为空或是栈顶元素小于取出值，这时将取出值压入辅助栈，然后继续从给定栈中取值，以此类推直至给定栈取空，这时候辅助栈就是排序完成的结果，返回即可，参见代码如下：

class Solution {
public:
    stack<int> sort(stack<int> s) {
        stack<int> res;
        while (!s.empty()) {
            int v = s.top(); s.pop();
            while (!res.empty() && res.top() > v) { //保证原栈中没有比v大的了
                s.push(res.top());
                res.pop();
            }
            res.push(v);
        }
        return res;
    }
};

设计一个接口，实现add getMedian 以及remove函数 add是将item进一个集合中，getMedian获取目前为止集合中的中位数

1. add直接添加，每个getMedian调用topK,时间复杂度是O(n)
2. add插入排序到有序数组中，getMedian每次直接O(1)去取
3. 维护两个堆，一个大顶堆，一个小顶堆，同时保证大顶堆的最大值比最小堆的最小值要小，同时保证两个堆的大小不能够差1
4. remove方法作为附加题，可以利用hash，存储每个元素和map，直接在堆中将该数字删除，同时调整堆的结构