给定长度为n的数列a[]和整数k，求b[i] = min{a[i], ... , a[i + k - 1]}, 复杂度为O(n)
最开始单调队列为空，保证队列中的元素始终保持单调性
为了计算b[0]，把0到k-1依次加入队列。在加入i时，当单调队列的末尾的值j满足a[j] >= a[i],则不断取出。直到双端队列为空或者a[j] < a[i]之后再于末尾加入i。
等到k-1加入队列，查看头部的值j，b[0] = a[j]。如果j = 0, 由于在之后的计算的中都不会用到了，因此从双端队列的头部删去。
接下里，为了计算b[i]，需要在双端队列的末尾加入k。不断加入元素，就可以算出后面的b[i]的值。
1 int n, k; 2 int a[maxn]; 3 4 int b[maxn]; 5 int deq[maxn]; 6 7 void solve() { 8 int s = 0, t = 0; 9 for (int i = 0; i < n; i++) {10 //在双端队列的末尾加入i11 while (s < t && a[deq[t - 1]] >= a[i]) t--;12 deq[t++] = i;13 if (i - k + 1 >= 0) {14 b[i - k + 1] = a[deq[s]];15 //从头部删除16 if (deq[s] == i - k + 1) {17 s++;18 }19 }20 }21 for (int i = 0; i <= n - k; i++) {22 printf("%d%d", b[i], i == n - k ? '\n' : ' ');23 }24 }
POJ2823
用两个双端队列维护
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define INF 0x3f3f3f3f 8 #define mod 1000000007 9 typedef long long LL;10 using namespace std;11 12 const int maxn = 1e6 + 10;13 14 int N, len;15 16 int a[maxn];17 18 int b[maxn];19 int deq[maxn];20 21 void GetMin() {22 int s = 0, t = 0;23 for (int i = 0; i < N; i++) {24 while (s < t && a[deq[t - 1]] >= a[i]) t--;25 deq[t++] = i;26 if (i - len + 1 >= 0) {27 b[i - len + 1] = a[deq[s]];28 if (deq[s] == i - len + 1) {29 s++;30 }31 }32 }33 34 for (int i = 0; i <= N - len; i++) {35 printf("%d%c", b[i], i == N - len ? '\n' : ' ');36 }37 }38 39 void GetMax() {40 int s = 0, t = 0;41 for (int i = 0; i < N; i++) {42 while (s < t && a[deq[t - 1]] <= a[i]) t--;43 deq[t++] = i;44 if (i - len + 1 >= 0) {45 b[i - len + 1] = a[deq[s]];46 if (deq[s] == i - len + 1) {47 s++;48 }49 }50 }51 52 for (int i = 0; i <= N - len; i++) {53 printf("%d%c", b[i], i == N - len ? '\n' : ' ');54 }55 }56 57 int main() {58 scanf("%d%d", &N, &len);59 for (int i = 0; i < N; i++) {60 scanf("%d", a + i);61 }62 GetMin();63 GetMax();64 return 0;65 }