标签：单调队列   poj   

单调队列典型题

An array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.

Window position Minimum value Maximum value
[1  3  -1] -3  5  3  6  7    -1   3  
 1 [3  -1  -3] 5  3  6  7    -3   3  
 1  3 [-1  -3  5] 3  6  7    -3   5  
 1  3  -1 [-3  5  3] 6  7    -3   5  
 1  3  -1  -3 [5  3  6] 7    3   6  
 1  3  -1  -3  5 [3  6  7]   3   7  

Your task is to determine the maximum and minimum values in the sliding window at each position.

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string> #include<map> #include<set> #define eps 1e-6 #define LL long long using namespace std; const int maxn = 2000000; //const int INF = 0x3f3f3f3f; int n, k; int a[maxn]; //单调队列 int qmin[maxn], vmin[maxn], hmin = 1, tmin = 0; void Min(int a, int i) { //第i个元素a入队 while(hmin<=tmin && vmin[hmin] <= i-k) hmin++; //超范围队首出队 //while(hmin<=tmin && qmin[tmin]>=a) tmin--; //不符合要求队尾出列 int l = hmin, r = tmin; while(l <= r) { int m = l+(r-l)/2; if(qmin[m] >= a) r = m - 1; else l = m + 1; } tmin = ++r; qmin[tmin] = a; vmin[tmin] = i; } int qmax[maxn], vmax[maxn], hmax = 1, tmax = 0; void Max(int a, int i) { //第i个元素a入队 while(hmax<=tmax && vmax[hmax] <= i-k) hmax++; //超范围队首出队 //while(hmax<=tmax && qmax[tmax]<=a) tmax--; //不符合要求队尾出列 int l = hmax, r = tmax; while(l <= r) { int m = l+(r-l)/2; if(qmax[m] <= a) r = m - 1; else l = m + 1; } tmax = ++r; qmax[tmax] = a; vmax[tmax] = i; } int ansMax[maxn], ansMin[maxn]; int main() { // freopen("input.txt", "r", stdin); while(scanf("%d%d", &n, &k) == 2) { hmin = 1, tmin = 0; hmax = 1, tmax = 0; for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i < k; i++) { Min(a[i], i); Max(a[i], i); } for(int i = k; i <= n; i++) { Min(a[i], i); ansMin[i-k] = qmin[hmin]; Max(a[i], i); ansMax[i-k] = qmax[hmax]; } for(int i = 0; i <= n-k; i++) if(i != n-k) printf("%d ", ansMin[i]); else printf("%d\n", ansMin[i]); for(int i = 0; i <= n-k; i++) if(i != n-k) printf("%d ", ansMax[i]); else printf("%d\n", ansMax[i]); } return 0; }

，