也就是有一个数列a，要求你求数列b和c，b[i]是a[i]…a[i+w-1]中的最小值，c[i]是最大值。如果a是1,3,-1,-3,5,3,6,7，则b为-1,-3,-3,-3,3,3，c为3,3,5,5,6,7。

这个问题相当于一个数据流（数列a）在不断地到来，而数据是不断过期的，相当于我们只能保存有限的数据（sliding window中的数据，此题中就是窗口的宽度w），对于到来的查询（此题中查询是每时刻都有的），我们要返回当前滑动窗口中的最大值\最小值。注意，元素是不断过期的。

解决这个问题可以使用一种叫做单调队列的数据结构，它维护这样一种队列：

a)从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增），比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。

满足以上两点的队列就是单调队列，首先，只有第一个元素的序列一定是单调队列。

那么怎么维护这个单调队列呢？无非是处理插入和查询两个操作。

对于插入，由于性质b，因此来的新元素插入到队列的最后就能维持b)继续成立。但是为了维护a)的成立，即元素在我们关注的指标下递减，从队尾插入新元素的时候可能要删除队尾的一些元素，具体说来就是，找到第一个大于（在所关注指标下）新元素的元素，删除其后所有元素，并将新元素插于其后。因为所有被删除的元素都比新元素要小，而且比新元素要旧，因此在以后的任何查询中都不可能成为答案，所以可以放心删除。

对于查询，由于性质b，因此所有该时刻过期的元素一定都集中在队头，因此利用查询的时机删除队头所有过期的元素，在不含过期元素后，队头得元素就是查询的答案（性质a），将其返回即可。

由于每个元素都进队出队一次，因此摊销复杂度为O(n)。

这个讲的十分清楚，我只是搬运