在这里先说一道微软的面试题目———《队列中的最大值》
让你设计一个队列，是其求里面最大值的时间复杂度尽可能的低，但这个队列除了最大值外，就是一个普通的队列，该怎么进出还是怎么进出，并不是优先队列。
对于一堆树，我们求其中最大值一般都会直接遍历一次，然后找到最大值，这样的话时间复杂度是O(n)，如果在这道题里面用这种方法总的时间复杂度会到O(n^2)，考虑到n的大小，这种方法显然是行不通的。有没有更为快速，可能有人想到使用堆，这也是优先队列使用的方法，如果实现的好的话，可以把时间复杂度从O(n)降到O(logn)，不过，我这里说的不是这种方法，我要来说一下时间复杂度为O(1)的一种算法。
在说这个算法之前，我先要讲两个东西———栈里面的最大值和用两个栈实现一个队列。
我们很容易可以把求栈里面的最大值问题的时间复杂度降到O(1)，我们在栈的每一个节点保存两个值Val和Max，一个是原来应该保存的值，另一个是max值，就是当这个节点是栈顶时栈中最大的值，如果新来一个数x，那么添加一个节点val = x， Max = max(stack.top().Max, x)，这样的话即使我们执行了多长pop操作也可以在O(1)的时间里求出里面的最大值，如果不明白请看下图。
比如说这就是一个有7个元素的栈，左边val就是原来的值，右边就是max，比如说当top指针如图所示，5就是栈里面最大的值，如果我们执行一次pop，我们还是可以一次得到栈里面最大的值。
关于用两个栈实现一个队列，如果将一串数分别入栈和入队列，然后出栈出队列，我们就会发现一个顺序反了，一个没有。如果我们用栈实现队列必须用两个栈，反一次，然后再反一次，不就正好是队列的顺序了吗？
然后我们姑且就称这个用栈实现的队列叫Queue吧，这样的话还有一个出人对列的问题，还记得出队列的顺序吗？先入的先出，那我们到底应该怎么实现呢？ 看看这个Queue里面吧， 里面有个两个栈，我们就叫In和Out栈吧。如下图
为什么是In和Out，因为，我们入Queue的时候把元素放的In栈里面，出Queue的时候从Out栈里面出，还有在出入Queue的时候适时把In里面的元素放到Out里面，适时到底是什么时候？ 就是出Queue的时候Out里面没有元素了，然后把In里面所有元素压的Out栈里面，注意是所有元素，这样才能保证他们出入Queue的顺序正好是一个出入队列的顺序。
说了这么多，我们在来看看这道题，一个区间每次向后移动一位，然后求里面的最大最小值，这个过程不就是先把最早进入区间的一个数去掉，然后加入一个数，这个不就是一个队列吗？？然后让你找队列里面的最大最小值（详情请参考《剑指offer》一书，具体多少页我忘记了） 有了上面两个知识，我们就可以在O(n)的时间复杂度里面解决这个问题了。
下面是解题代码，不过还是超时了，我想可能是因为多次调用函数的原因，思路是完全正确的，大家可以尝试把那些东西写一起，还有这个题的输入输出数据量极大，不要用cin cout输入输出，不然会超时的。
备注：这道题貌似可以用动态规划的方法做，不过本弱菜不会，如有读者会希望不吝赐教。
//poj 2823 //2013-08-03-10.39 #include <stdio.h> #include <stack> #include <algorithm> #define maxn 1000006 using namespace std; int maxv[maxn]; int minv[maxn]; int cnt; struct node { int val, maxv, minv; }; stack<node> sin; stack<node> sout; void push(int v) { if (sin.empty()) { node tmp; tmp.val = v; tmp.maxv = v; tmp.minv = v; sin.push(tmp); } else { node tmp = sin.top(); tmp.val = v; tmp.maxv = max(tmp.maxv, v); tmp.minv = min(tmp.minv, v); sin.push(tmp); } } void pop() { if (sout.empty()) { while (!sin.empty()) { node tmp = sin.top(); sin.pop(); if (sout.empty()) { tmp.maxv = tmp.val; tmp.minv = tmp.val; sout.push(tmp); } else { node tmp2 = sout.top(); tmp.maxv = max(tmp2.maxv, tmp.val); tmp.minv = min(tmp2.minv, tmp.val); sout.push(tmp); } } sout.pop(); } else { sout.pop(); } } void getval() { if(!sin.empty() && !sout.empty()) { node tin = sin.top(), tout = sout.top(); minv[cnt] = min(tin.minv, tout.minv); maxv[cnt] = max(tin.maxv, tout.maxv); cnt++; } if (sin.empty() && !sout.empty()) { node tout = sout.top(); minv[cnt] = tout.minv; maxv[cnt] = tout.maxv; cnt++; } if (!sin.empty() && sout.empty()) { node tin = sin.top(); minv[cnt] = tin.minv; maxv[cnt] = tin.maxv; cnt++; } } int main() { int n, k; while (scanf("%d %d", &n, &k) != EOF) { int tmp; cnt = 1; while (!sin.empty()) sin.pop(); while (!sout.empty()) sout.pop(); for (int i = 1; i <= n; i++) { scanf("%d", &tmp); push(tmp); if (i == k) { getval(); } if (i > k) { pop(); getval(); } } for (int i = 1; i < cnt; i++) { if (i == 1) printf("%d", minv[i]); else printf(" %d", minv[i]); } puts(""); for (int i = 1; i < cnt; i++) { if (i == 1) printf("%d", maxv[i]); else printf(" %d", maxv[i]); } puts(""); } return 0; }
