题目描述
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
样例
输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
单调队列
模拟队列
1.队列结构:后进先出
2.操作:在队尾插入元素,队头弹出元素
3.实现:数组模拟.hh:队头下标;tt:队尾下标
C++ 代码
#include<cstdio>
#include<cstring>
const int Max_N = 1e5 + 10;
int q[Max_N], tt = -1, hh = 0;
void push(int x)
{
q[++tt] = x;//在队尾插入
}
void pop()
{
hh++; //在队头删除
}
int front()
{
return q[hh];
}
bool empty()
{
return hh > tt;
}
int main()
{
int T,x;
char op[10];
scanf("%d",&T);
while( T-- )
{
scanf("%s",op);
if( !strcmp(op,"push") )
{
scanf("%d",&x);
push(x);
}
else if( !strcmp(op,"empty") )
{
if( empty() ) puts("YES");
else puts("NO");
}
else if( !strcmp(op,"query") ) printf("%d\n",front());
else pop();
}
return 0;
}
单调队列
1.首先考虑朴素的队列:先在队列插入k个元素,每次遍历所有元素找到最小/最大;弹出队头,在队尾插入
下一个元素.时间复杂度O(nk)
2.考虑计算时有无冗余:以求最小值为例,样例的第一个区间1 3 -1 ,因为题目要求区间内部的最小值,
那么两种元素优先考虑:1.更靠右,其生存期更长;2.更小.所以队列中的1 3是冗余元素,因为在窗口滑动的
过程中我们不可能考虑到它们.
3.冗余元素性质:i<j,a[i]>=a[j],每次加入新元素时,我们都依次把队头且值更大的元素弹出.
最后的序列符合:i<j且a[i]<a[j],单调性出现;当最左端元素超出窗口时要删去,所以要对序列两端操作,
用单调队列实现.
4.实现时维护符合上述条件的单调队列,队列元素为序列中的下标.
时间复杂度
从前向后扫描,总的插入删除操作不超过n,所以时间复杂度O(n)
C++ 代码
#include<cstdio>
const int Max_N = 1e6 + 10;
int n, k;
int a[Max_N];
int q[Max_N], hh, tt = -1;
int main()
{
scanf("%d%d",&n,&k);
for( int i = 0; i < n; i++ ) scanf("%d",&a[i]);
for( int i = 0; i < n; i++ )
{
if( tt>=hh && q[hh]<i-k+1 ) hh++; //队头超出窗口(每次最多一个 所以只需要if)
while( tt>=hh && a[q[tt]]>=a[i] ) tt--;//弹出队尾逆序元素
q[++tt] = i;//插入i
if( i>=k-1 ) printf("%d ",a[q[hh]]);
}
puts("");
//对称操作
tt = -1, hh = 0;
for( int i = 0; i < n; i++ )
{
if( tt>=hh && q[hh]<i-k+1 ) hh++;
while( tt>=hh && a[q[tt]]<=a[i] ) tt--;
q[++tt] = i;
if( i>=k-1 ) printf("%d ",a[q[hh]]);
}
puts("");
return 0;
}