2823 -- Sliding Window
单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。
http://blog.csdn.net/kenden23/article/details/37598147
Read full article from 2823 -- Sliding Window
An array of size n ≤ 106 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.
Your task is to determine the maximum and minimum values in the sliding window at each position.
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 |
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
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 7http://www.cnblogs.com/zhexipinnong/archive/2012/05/01/2477852.html
单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。
一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：
1. 在原数列中的位置（下标）
2. 他在动态规划中的状态值
而单调队列则保证这两个值同时单调。
从以上看，单调队列的元素最好用一个类来放，不这样的话，就要开两个数组。。。
插入方法（以最大单调队列为例）：
在插入一个元素前，先判断队列是否为空（head<=tail），然后再判断队尾元素是否比要插入的元素小（q[tail].val<data[insert]），如果是的话，则将队尾元素删除（--tail）。
重复以上过程，直至为空或队尾元素比其大。
删除方法：
这个要根据具体题目而定。在本题是如果当前的INDEX与队首的INDEX相差大于等于K，则删除。
3 int a[MAXN],bque[MAXN],sque[MAXN]; 4 int n,k; 5 void getmax() 6 { 7 int i,head = 1,tail = 1; 8 for(i = 1;i < k;i++) 9 { 10 while(tail >= head && a[i] > a[bque[tail]])//队列不为空且当前元素大于队尾元素 11 tail--;//删除队尾元素 12 tail++; 13 bque[tail] = i; 14 } 15 for(i = k;i <= n;i++) 16 { 17 while(tail >= head && i - bque[head] >= k)//队列不为空，且当前元素下标减去队首元素的下标>=k 18 head++;//删除队首元素 19 while(tail >= head && a[i] > a[bque[tail]])//队列不为空且当前元素大于队尾元素 20 tail--; 21 tail++; 22 bque[tail] = i; 23 if(i != n) 24 printf("%d ",a[bque[head]]); 25 } 26 printf("%d\n",a[bque[head]]); 27 } 28 void getmin() 29 { 30 int i,head = 1,tail = 1; 31 for(i = 1;i < k;i++) 32 { 33 while(tail >= head && a[i] < a[sque[tail]]) 34 tail--; 35 tail++; 36 sque[tail] = i; 37 } 38 for(i = k;i <= n;i++) 39 { 40 while(tail >= head && i - sque[head] >= k) 41 head++; 42 while(tail >= head && a[i] < a[sque[tail]]) 43 tail--; 44 tail++; 45 sque[tail] = i; 46 if(i != n) 47 printf("%d ",a[sque[head]]); 48 } 49 printf("%d\n",a[sque[head]]); 50 } 51 int main() 52 { 53 while(~scanf("%d%d",&n,&k)) 54 { 55 for(int i = 1;i <= n;i++) 56 scanf("%d",&a[i]); 57 getmin(); 58 getmax(); 59 } 60 return 0; 61 }http://www.programerhome.com/?p=29776
http://blog.csdn.net/kenden23/article/details/37598147
本题是单调队列题解的入门，当然也可以使用RMQ 和 线段树，不过速度都没有单调队列那么快。
单调队列难点：
1 如何入列，保存数据 -- 最小单调队列的时候， 所有数都入列一次，在新的数据准备入列的时候，增加判断，如果当前数值小于队尾数值，那么队尾数值就出列。空队列的时候直接入列。
- void getMins()
- {
- int tail = 0, head = 1; //初始化tail<head表示为空列
- for (int i = 1; i < K; i++) //初始化单调队列
- {
- while (tail >= head && qu[tail] >= arr[i]) tail--;
- qu[++tail] = arr[i]; //记录可能的答案值
- index[tail] = i; //记录额外需要判断的信息
- }
- for (int i = K; i <= N; i++)
- {
- while (tail >= head && qu[tail] >= arr[i]) tail--; //不符合条件出列
- qu[++tail] = arr[i];
- index[tail] = i;
- while (index[head] <= i-K) head++;
- ans[i-K] = qu[head]; //ans从下标0开始记录
- }
- }
- void getMaxs()
- {
- int tail = 0, head = 1;
- for (int i = 1; i < K; i++) //初始化单调队列
- {
- while (tail >= head && qu[tail] <= arr[i]) tail--;
- qu[++tail] = arr[i];
- index[tail] = i;
- }
- for (int i = K; i <= N; i++)
- {
- while (tail >= head && qu[tail] <= arr[i]) tail--; //不符合条件出列
- qu[++tail] = arr[i];
- index[tail] = i;
- while (index[head] <= i-K) head++;
- ans[i-K] = qu[head]; //ans从下标0开始记录
- }
- }
const int N = 1e6 + 5;
int a[N], q[N], t[N];
int front, rear, n, k;
#define NOTMONO (!op && a[i] < q[rear - 1]) || (op && a[i] > q[rear - 1])
void getMonoQueue(int op) //op = 0 时单增队列 op = 1 时单减队列
{
front = rear = 0;
for(int i = 0; i < n; ++i)
{
while( rear > front && (NOTMONO)) --rear;
t[rear] = i; //记录滑窗滑到i点的时间
q[rear++] = a[i];
while(t[front] <= i - k) ++front; //保证队首元素在滑窗之内
if(i > k - 2)
printf("%d%c", q[front], i == n - 1 ? '\n' : ' ');
}
}
int main()
{
while (~scanf("%d%d", &n, &k))
{
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
getMonoQueue(0); //单增队列维护最小值
getMonoQueue(1); //单减队列维护最大值
}
return 0;
}
https://www.programering.com/a/MDMzITMwATg.htmlRead full article from 2823 -- Sliding Window
