POJ 2823 Sliding Window(单调队列)

/*单调队列适合解决的问题，多次查询k个连续序列中最大或最小值。可以将复杂度从O(n*n)缩短到O(n)。实现模式：队列实现，只不过其中元素单调（依次增大或减小），我们假设求最大值。入队时比较队尾元素与插入元素的大小，如果队尾元素小与插入元素，则对尾元素出对，直到大于等于位置。这样插入k个元素后，队列中队首即为最大值。继续进行第二次查询时，需要比较队首元素在原来元素中的位置，判断是否在这次查询的区间内，如果不在，则出对。使用自定义数组即可实现。*/#include <iostream>using namespace std;const int nMax = 1000010;int s[nMax];int n, k;struct Queue{int pos;int v;Queue(){}Queue(int pos, int v):pos(pos), v(v){}}MinQueue[nMax], MaxQueue[nMax];//一个最小队列，一个最大队列int MinLeft, MinRight;int MaxLeft, MaxRight;int main(){//freopen("e://data.txt", "r", stdin);while(scanf("%d%d", &n, &k) != EOF){if(!n || !k) continue;int i;for(i = 0;i < n; ++ i)scanf("%d", &s[i]);MinLeft = MinRight = MaxLeft = MaxRight = 0;//MinQueue[MinRight ++] = Queue(i, s[i]);for(i = 0; i < k; ++ i)//队列初始化，其实可以跟下面的合并{while(MinRight > 0 && MinQueue[MinRight - 1].v > s[i])MinRight --;MinQueue[MinRight ++] = Queue(i, s[i]);}printf("%d", MinQueue[MinLeft].v);for(i;i < n; ++ i){if(MinQueue[MinLeft].pos < i - k + 1)//判断队首元素是否还在查询范围之内MinLeft ++;while(MinRight > MinLeft && MinQueue[MinRight - 1].v > s[i])//循环比较队尾元素与插入元素的大小，直到对尾元素大于等于插入元素或者队为空MinRight --;MinQueue[MinRight ++] = Queue(i, s[i]);//入队printf(" %d", MinQueue[MinLeft].v);}printf("\n");for(i = 0; i < k; ++ i)//与上面求最小值相同{while(MaxRight > 0 && MaxQueue[MaxRight - 1].v < s[i])MaxRight --;MaxQueue[MaxRight ++] = Queue(i, s[i]);}printf("%d", MaxQueue[MaxLeft].v);for(i;i < n; ++ i){if(MaxQueue[MaxLeft].pos < i - k + 1)MaxLeft ++;while(MaxRight > MaxLeft && MaxQueue[MaxRight - 1].v < s[i])MaxRight --;MaxQueue[MaxRight ++] = Queue(i, s[i]);printf(" %d", MaxQueue[MaxLeft].v);}printf("\n");}return 0;}