AcWing 154. 滑动窗口
原题链接
简单
作者:
Karma
,
2019-10-24 17:43:30
,
所有人可见
,
阅读 761
// 此题有两个要点:
// 首先:判断单调队列的首元素是否要弹出(判断依据为滑动窗口范围)
// 其次:求最小值时,加入当前位置的下标时保证队列中的下标所对应的值递增(求最大值时需要保证递减)
#include <iostream>
#include <vector>
using namespace std;
vector<int> ivec(1e6);
// 队列中存放数组的下标
// 求最小值时,
// 队列的首元素永远存放滑动窗口中的最小值的下标,
// 队列中存放的下标对应的值递增。
// 求最大值时相反
vector<int> q(1e6);
int main()
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n; ++ i)
{
cin >> ivec[i];
}
int head = 0;
int tail = 0;
// 求最小
for(int i = 0; i < n; ++ i)
{
// 现在要处理下标为i的值
// i-k+1 为滑动窗口最左端的下标,
// 该队列中其实只有首元素有用,
// 代表最小值的下标,
// 队列中的其它元素不用管。
// 注意:此处为q[head]
if(head < tail && i-k+1 > q[head])
{
++ head;
}
// 要将i放入队列中,需要先保证下标代表的值递增。
// 此步骤将不满足条件的下标弹出。
// 注意:弹出尾元素,不能使用stl的queue
// 此处可以没有=号
while(head < tail && ivec[i] <= ivec[q[tail-1]])
{
-- tail;
}
// 放入i
q[tail] = i;
++ tail;
// 如果滑动窗口是满的,才输出
if(i-k+1 >= 0)
{
cout << ivec[q[head]] << " ";
}
}
cout << endl;
// 求最大
head = 0;
tail = 0;
for(int i = 0; i < n; ++ i)
{
if(head < tail && i-k+1 > q[head])
{
++ head;
}
while(head < tail && ivec[i] >= ivec[q[tail-1]])
{
-- tail;
}
q[tail] = i;
++ tail;
if(i-k+1 >= 0)
{
cout << ivec[q[head]] << " ";
}
}
cout << endl;
}