队列，栈，Sliding Window

起初是有两道很eggache的面试题。

1. Use two Stacks to implement a Queue
2. Use two Queues to implement a Stack

先不管效率高不高，FIFO与LILO之间的相互变化，这个题目还是很有趣的。
栈，将一个输入数列反序；队列，正序输出一个数列；而反反得正，这便是解决问题的关键。
比如第1题，LILO->FIFO，有栈S1，S2：
（1）在入队时，将元素push到S1中；（2）在出队时，如果S2非空，则从S2中pop，否则将S1中所有元素依次pop，push到S2中，再出栈。
 

而后，又有两个看起来很实用的题目。

3. Implement a Stack with extract minimum value operation
4. Implement a Queue with extract minimum value operation

实现一个栈或者队列，拥有查询其中最小值的功能。
对于第3题，可以试想：
如果后入栈的元素比先入栈的元素小，那么它可能是当前栈的最小值；但是如果后入栈的元素比先入栈的元素大，它肯定不会是当前栈的最小值。
以此，维护这样一个栈就可以达到实时查询最小值的功能。

一个细节处理是，维护的这个最小值栈，可以存储的是元素的位置，这样我在pop原始元素栈时，可以检查存储最小值的栈是否也应该pop。

然而，另一种处理是，我依旧可以在维护的最小值的栈里存放元素的值，只是相同的最小值，我们也保存在栈中。
因为这个栈里的元素的大小关系一定是单调不增的。
这样，在原始元素出栈时，原始元素栈栈顶的元素一定是大于等于最小值栈顶的元素的。如果相等，我们同时pop两个栈的元素；如果不等，只pop原始元素栈。

vector<int> origin, min;

void ins(int el)
{
        if (!min.empty() && min.back() < el) return;
        else min.push_back(el); 
}

void del(int el)
{
        if (el == min.back()) min.pop_back();
        origin.pop_back();
}

 第二种处理方法在处理第4个，队列最小值的问题时，要更加方便，因为队列元素的位置一直在变化。尤其是在循环队列时。

 进一步，了解到一个应用很广的算法，Sliding Window。

 5. 有N个元素，有一个W大小的窗口。窗口沿着序列从左边向右边滑动。设计一种方法，快速计算出窗口中的元素的最小值或最大值。

 这个问题，其实就是上面的第4个问题。和栈的处理情况同样的想法。

 另一个有一点变化的问题是：

 6. 一条项链上有N个珠子。珠子上有两种记号，C或者J。
 我们需要从任意一个位置将这条项链剪开，从左边或者右边取下这些珠子（一次只能从一边一直取完）。
 在取下这些珠子时，我们必须保证，任意时刻，取下的C号珠子的个数都不小于取下的J号珠子的个数。
 试问，满足这样条件的，剪开项链的位置有多少个？

 我们为了计算取下珠子记号个数的条件，将每个C号珠子记为1，J号记为-1。
 这样，从一个位置剪开，从一边取下珠子的过程，就转化为计算这个方向上，1，-1序列的累加和的过程。
 过程中，保证累加和总是大于0，这就是一个可行的剪开位置。

 直接模拟的时间复杂度是O（N^2）。对于N=10^6时，我们需要进一步的改进。

 注意到，依次尝试每个相邻的剪开位置时，这些1，-1序列产生的累加和之间，依次只相差了个1或者-1。

 比如设从位置0开始的累加和序列分别为a0, a1, ... , a(N-1)
 假设位置0的元素是1，那么从位置1开始的累加和序列即为a1-1, a2-1, ... , a(N-2)-1, a(N-1)-1, a(N-1)（即sum，所有元素的和）

 由此，这个依次递推的过程又演变成了一个大小为N的滑动窗口。
 用offset记录相对于最初的序列和的偏移。每次递推时，我们删去第一个元素，加入一个新的元素sum+offset。
 利用上述的第4题中的方法，计算窗口中的最小值，若其是大于等于0的，那么这就是一个可行的剪开位置。 时间复杂度O（N）。

总结：简单的数据结构也会有这么好的应用。自感孤陋寡闻之时，我也将继续探索下去。