very very very easy ,very very easy,very easy 题单要讲的举手。
我们先从 easy 题单讲起。
今日知识,单调队列。
假如序列 a 是 1\ 3\ -1\ -3\ 5\ 3\ 6\ 7 , k 是 2 要求最大值。
首先把 1 加进来,然后继续往后看,把 3 加进来,这时可以发现滑动窗口是往右滑的,所以 1 比 3 更早地从滑动窗口里出去,而 3 比 1 打所以, 1 在后面不可能成为答案,所以可以直接把 1 删了。
现在我们队列里的数字有 3 所以答案是 3 。
再加入 -1 现在队列里是 3\ -1 答案是 3 。
然后加入 -3 现在队列里是 3\ -1\ -3 ,但是这时滑动口的位置是 3 到 4 ,所以要把 3 删了,答案是 -1 ,以此类推。
核心代码
for(int i=1;i<=n;++i)
{
while(h<=t&&a[i]<=a[q[t]]) t--;
q[++t]=i;
while(h<=t&&i-q[h]>=k) h++;
if(i>=k) printf("%d ",a[q[h]]);
}
如果有一个人比你小,还比你强,那么你就要被单调队列 pop 了。
祝大家在学习的时候不要被 pop 。