思路：
最小值和最大值分开来做，两个for循环完全类似，都做以下四步：
解决队首已经出窗口的问题;
解决队尾与当前元素a[i]不满足单调性的问题;
将当前元素下标加入队尾;
如果满足条件则输出结果;
需要注意的细节：
上面四个步骤中一定要先3后4，因为有可能输出的正是新加入的那个元素;
队列中存的是原数组的下标，取值时要再套一层，a[q[]];
算最大值前注意将hh和tt重置;
此题用cout会超时，只能用printf;
hh从0开始，数组下标也要从0开始。
include
using namespace std; const int N = 1000010; int a[N], q[N], hh, tt = -1; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; ++ i) { scanf(“%d”, &a[i]); if (i - k + 1 > q[hh]) ++ hh; // 若队首出窗口，hh加1 while (hh <= tt && a[i] <= a[q[tt]]) – tt; // 若队尾不单调，tt减1 q[++ tt] = i; // 下标加到队尾 if (i + 1 >= k) printf("%d “, a[q[hh]]); // 输出结果 } cout << endl; hh = 0; tt = -1; // 重置！ for (int i = 0; i < n; ++ i) { if (i - k + 1 > q[hh]) ++ hh; while (hh <= tt && a[i] >= a[q[tt]]) – tt; q[++ tt] = i; if (i + 1 >= k) printf(”%d ", a[q[hh]]); } return 0; } #include using namespace std; const int N = 1e6 + 10; int n, k, q[N], a[N];//q[N]存的是数组下标 int main() { int tt = -1, hh=0;//hh队列头 tt队列尾 cin.tie(0); ios::sync_with_stdio(false); cin>>n>>k; for(int i = 0; i <n; i ++) cin>>a[i]; for(int i = 0; i < n; i ++) { //维持滑动窗口的大小 //当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的 //滑动窗口的大小(k),队列弹出队列头元素以维持滑动窗口的大小 if(hh <= tt && k < i - q[hh] + 1) hh ++; //构造单调递增队列 //当队列不为空(hh <= tt) 且 当队列队尾元素>=当前元素(a[i])时,那么队尾元素 //就一定不是当前窗口最小值,删去队尾元素,加入当前元素(q[ ++ tt] = i) while(hh <= tt && a[q[tt]] >= a[i]) tt --; q[ ++ tt] = i; if(i + 1 >= k) printf(“%d “, a[q[hh]]); } puts(””); hh = 0,tt = -1; for(int i = 0; i < n; i ++) { if(hh <= tt && k < i - q[hh] + 1) hh ++; while(hh <= tt && a[q[tt]] <= a[i]) tt --; q[ ++ tt] = i; if(i + 1 >= k ) printf("%d ", a[q[hh]]); } return 0; }
无注释版
#include using namespace std; int h,t=-1; const int N=1e6+10; int a[N],q[N]; int main() { int n,k; cin>>n>>k; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) { if(h<=t && i-q[h]+1>k) h++; while(h<=t && a[q[t]]>=a[i]) t–; q[++t]=i; if(i+1>=k) cout<<a[q[h]]<<’ ‘; } cout<<endl; h=0;t=-1; for(int i=0;i<n;i++) { if(h<=t && i-q[h]+1>k) h++; while(h<=t && a[q[t]]<=a[i]) t–; q[++t]=i; if(i+1>=k) cout<<a[q[h]]<<’ '; } return 0; }
无注释版2
#include using namespace std; const int N=1e6+10; int que[N],head,tail,a[N]; int main() { int n,k; cin>>n>>k; for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) { if(tail-head>0 && i-que[head]+1>k) head++; while(tail-head>0 && a[que[tail-1]]>=a[i]) tail--; que[tail++]=i; if(i>=k-1) cout<<a[que[head]]<<' '; } cout<<endl; tail=head=0; for(int i=0;i<n;i++) { if(tail-head>0 && i-que[head]+1>k) head++; while(tail-head>0 && a[que[tail-1]]<=a[i]) tail--; que[tail++]=i; if(i>=k-1) cout<<a[que[head]]<<' '; }
}
