Description
| 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.
Input
Output
Sample Input
8 3 1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7
题意：
一个长度为n的序列，用长度为看k的窗口在上面移动，求窗口中数字最大为多少。
分析：
单调队列求，入门题目收下了。、
1 # include <iostream> 2 using namespace std; 3 4 const int MAX = 1000010; 5 int a[MAX]; 6 int q[MAX]; 7 int p[MAX]; 8 int Min[MAX]; 9 int Max[MAX]; 10 11 int n, k; 12 13 void get_Min() 14 { 15 int head = 1, tail = 0; 16 for(int i = 0; i < k - 1; i++) 17 { 18 while(head <= tail && q[tail] >= a[i]) 19 tail--; 20 tail++; 21 q[tail] = a[i]; 22 p[tail] = i; 23 } 24 for(int i = k - 1; i < n; i++) 25 { 26 while(head <= tail && q[tail] >= a[i]) 27 tail--; 28 tail++; 29 q[tail] = a[i]; 30 p[tail] = i; 31 while(p[head] < i - k + 1) 32 { 33 head++; 34 } 35 Min[i - k + 1] = q[head]; 36 } 37 } 38 void get_Max() 39 { 40 int head = 1, tail = 0; 41 for(int i = 0; i < k - 1; i++) 42 { 43 while(head <= tail && q[tail] <= a[i]) 44 tail--; 45 tail++; 46 q[tail] = a[i]; 47 p[tail] = i; 48 } 49 for(int i = k - 1; i < n; i++) 50 { 51 while(head <= tail && q[tail] <= a[i]) 52 tail--; 53 tail++; 54 q[tail] = a[i]; 55 p[tail] = i; 56 while(p[head] < i - k + 1) 57 { 58 head++; 59 } 60 Max[i - k + 1] = q[head]; 61 } 62 } 63 64 65 66 int main() 67 { 68 scanf("%d%d", &n, &k); 69 for(int i = 0; i < n; i++) 70 scanf("%d", &a[i]); 71 get_Min(); 72 get_Max(); 73 for(int i = 0; i < n - k + 1; i++) 74 { 75 if(i == 0) 76 printf("%d", Min[i]); 77 else 78 printf(" %d", Min[i]); 79 } 80 printf("\n"); 81 for(int i = 0; i < n - k + 1; i++) 82 { 83 if(i == 0) 84 printf("%d", Max[i]); 85 else 86 printf(" %d", Max[i]); 87 } 88 printf("\n"); 89 return 0; 90 }
原文：http://www.cnblogs.com/lyf-acm/p/5831093.html
