克拉玛依建设局官方网站/我赢网seo优化网站

题意：移动窗口，求一个窗口中最大值，最小值

暴力：

如果是暴力来做的话，时间复杂度是O(n)，是会超时的，所以应该思考别的办法

单调队列：

• 先想想一般的队列怎么做？
• 哪些点永远不会被用到，可以被删除，维护队列的单调性
• 优化后的取max，min时间复杂度时O(1)

一般队列怎么做？以求min为例

先滑动到窗口长度为k，再进行优化

发现，如果一个数他比 窗口内 所有左边的数都小，那么左边的数是永远不会被用到的

例如，-1比1，3都小，求最小值的时候1，3永远是不会被用到的

可以发现：每当一个数入队的时候，队列内所有比他大的元素都应该出队，然后自己再入队

while(hh<=tt&&a[q[tt]]>=a[i]) tt--;q[++tt]=i;

所以可以发现，最后队列具有一个单调性：单调上升

 因为比他小的数不会出队，最后在队列内的数是：

都在窗口内，且单调上升的

每次开始前应该把所有不在窗口内的数删除

if(hh<=tt&&i-k+1>q[hh])  hh++;

求max其实就是和min反过来了

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;int q[N],a[N];
int hh,tt;  //head,tailint main()
{int n,k;cin>>n>>k;for(int i=0;i<n;i++)cin>>a[i];hh=0,tt=-1;for(int i=0;i<n;i++){if(hh<=tt&&i-k+1>q[hh])  hh++;while(hh<=tt&&a[q[tt]]>=a[i]) tt--;q[++tt]=i;
//窗口滑动大小到k时才需要操作if(i>=k-1) cout<<a[q[hh]]<<' ';}cout<<endl;hh=0,tt=-1;for(int i=0;i<n;i++){if(hh<=tt&&i-k+1>q[hh]) hh++;while(hh<=tt&&a[q[tt]]<=a[i]) tt--;q[++tt]=i;if(i>=k-1) cout<<a[q[hh]]<<' ';}return 0;
}