在这里先说一道微软的面试题目———《队列中的最大值》
让你设计一个队列，是其求里面最大值的时间复杂度尽可能的低，但这个队列除了最大值外，就是一个普通的队列，该怎么进出还是怎么进出，并不是优先队列。
对于一堆树，我们求其中最大值一般都会直接遍历一次，然后找到最大值，这样的话时间复杂度是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;
}
