题解 P1886 【滑动窗口】
Xiefan_Guo
2019-08-10 21:15:47
**经典的单调队列问题**
单调队列需要满足的条件：
* 队列中的元素其对应在原来的列表中的顺序必须是单调递增的。
* 队列中元素的大小必须是单调递(增/减/自定义)。
---
$que[]$ 表示单调队列，$id[]$ 表示所对应在原列表里的序号。
> 当然，实际上只保留 $id[]$ 就足够了。一般的我们也时这么做的。
对于样例我们有：
```
8 3
1 3 -1 -3 5 3 6 7
```
1. 此时队中没有一个元素，我们令 $1$ 进队。 $que=\{1\},id=\{1\}$ 。
2. 假如把 $3$ 放进去，如果后面 $2$ 个数都比它大，那么 $3$ 就有可能成为最小的。此时，$que=\{1,3\},id=\{1,2\}$。
3. $que=\{-1\},id=\{3\}$。
4. $que=\{-3\},id=\{4\}$。
5. $que=\{-3,5\},id=\{4,5\}$。
6. $que=\{-3,3\},id=\{4,6\}$。
7. $que=\{3,6\},id=\{6,7\}$。
8. $que=\{3,6,7\},id=\{6,7,8\}$。
```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int que[maxn], id[maxn], a[maxn];
int n, k;
void solve_min()
{
int l = 1, r = 1;
for(int i = 1 ; i <= n; i++){
while(l < r && a[i] < que[r - 1])
r--;
que[r] = a[i];
id[r++] = i;
while(id[l] <= i - k)
l++;
if(i >= k) printf("%d%c", que[l], i == n ? '\n' : ' ');
}
}
void solve_max()
{
int l = 1, r = 1;
for(int i = 1 ; i <= n; i++){
while(l < r && a[i] > que[r - 1])
r--;
que[r] = a[i];
id[r++] = i;
while(id[l] <= i - k)
l++;
if(i >= k) printf("%d%c", que[l], i == n ? '\n' : ' ');
}
}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
solve_min();
solve_max();
return 0;
}
```