POJ 2823 Sliding Window(单一队列)
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; }